• 问题来源
• 问题简介

  给你一系列字符串stickers，问要在stickers中找多少个字符串（可重复使用）才能找到足够的字符（不可重复使用）拼出target字符串。若无法拼出则返回-1。

解题思路

Code

class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        // 令int值的每一位代表target在相应位置是否已被填充，则总共有1 << N个状态
        int N = target.length(), len_dp = 1 << N;
        // 到达每个状态的步数为-1
        vector<int> dp(len_dp, -1);
        // 初始状态为 0，步数为0
        dp[0] = 0;

        // 每个状态都是由前面的状态而来
        for (int i = 0; i < len_dp; i++) {
            // 遍历每个状态，并转移状态
            if (dp[i] == -1) {
                continue;
            }

            for (auto str : stickers) {
                int nowState = i;

                for (char letter : str) {
                    for (int j = 0; j < N; j++) {
                        if (nowState & (1 << j)) {
                            // 该位已被填充
                            continue;
                        }
                        if (target[j] == letter) {
                            // 填充该位
                            nowState |= (1 << j);
                            break;
                        }
                    }
                }

                // 状态已转移
                if (dp[nowState] == -1 || dp[nowState] > dp[i] + 1) {
                    dp[nowState] = dp[i] + 1;
                }
            }

        }

        return dp[len_dp-1];
    }
};

运行结果