691. Stickers to Spell Word

问一下target有没有长度限制！！
用这个 dp + memo O(N + N² + … + N^T) = O((N * (N^T - 1) / (N - 1))即每一层有N次循环 一共T层 N是sticker个数 T是target长度
cache[target]是所求结果，cache[“”] = 0
对每个sticker统计字母频
对每一层的target统计字母频
用每一个sticker去尝试拼凑部分target，拼不上的部分组成新的target再递归
遍历所有的可能，不断更新最小值即可

class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = stickers.size();
        vector<vector<int>> m(n, vector<int>(26));
        for (int i = 0; i < n; ++i) {
            for (char c : stickers[i]) {
                ++m[i][c - 'a'];
            }
        }
        int res = dfs(m, target);
        return res == INT_MAX ? -1 : res;
    }

    long dfs(const vector<vector<int>> &m, const string &target) {
        if (target.empty()) return 0;
        if (cache.count(target)) return cache[target];
        vector<int> mt(26);
        for (char c : target) {
            ++mt[c - 'a'];
        }
        int n = m.size();
        long res = INT_MAX; // 把当前结果初始化为INT_MAX
        for (int i = 0; i < n; ++i) {
            // if (m[i][target[0] - 'a'] == 0) continue; // 这个优化剪枝很神奇，可以避免潜在的对target完全没有贡献的sticker，暂时无法贡献的sticker等到其他sticker把部分target拼凑出来以后再贡献
            string s;
            for (int j = 0; j < 26; ++j) {
                if (mt[j] > m[i][j]) { // 这里大于或者大于等于无异，因为是要去掉当前sticker中可以拼成target的字母，所以如果sticker中的某个对应字母比target中的多，那么新组成的target就不需要添加该字母，所以只需要考虑sticker中对应字母不够拼成target的情况
                    s.append(mt[j] - m[i][j], 'a' + j);
                }
            }
            if (s == target) continue; // 如果没有之前那个优化，一定要判断新target和原target是否一样，避免重复递归
            res = min(res, dfs(m, s) + 1);
        }
        return cache[target] = res;
    }

    unordered_map<string, long> cache;
};

状态压缩dp O(2ⁿ*(S+n*s)) n是target长度 S是stickers所有字母个数 s是stickers的个数
target从一个字母都找不到匹配到所有字母都匹配上一共2ⁿ个状态

class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = target.length();
        vector<int> f(1 << n, -1);
        f[0] = 0;
        for (int state = 0; state < (1 << n); ++state) {
            if (f[state] == -1) continue;
            for (const auto &s : stickers) {
                int now = state;
                int m[26] = {0};
                for (char c : s) {
                    ++m[c - 'a'];
                }
                for (int i = 0; i < n; ++i) {
                    if ((now >> i) & 1) continue;
                    if (m[target[i] - 'a']-- > 0) { // 用在哪个位置上无所谓，最后结果不影响
                        now |= (1 << i);
                    }
                }
                if (f[now] == -1 || f[now] > f[state] + 1) {
                    f[now] = f[state] + 1;
                }
            }
        }
        return f.back();
    }
};

状态压缩dp O(2ⁿ*n*S) n是target长度 S是stickers所有字母个数
target从一个字母都找不到匹配到所有字母都匹配上一共2ⁿ个状态

class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = target.length();
        vector<int> f(1 << n, -1);
        f[0] = 0;
        for (int state = 0; state < (1 << n); ++state) {
            if (f[state] == -1) continue;
            for (const auto &s : stickers) {
                int now = state;
                for (char c : s) {
                    for (int i = 0; i < n; ++i) {
                        if ((now >> i) & 1) continue;
                        if (target[i] == c) {
                            now |= (1 << i);
                            break;
                        }
                    }
                }
                if (f[now] == -1 || f[now] > f[state] + 1) {
                    f[now] = f[state] + 1;
                }
            }
        }
        return f.back();
    }
};