691. Stickers to Spell Word

https://leetcode.com/problems/stickers-to-spell-word/

用stickers给出的单词，可重复使用并能拆成任何小段，问至少需要几个stickers内的单词可拼出给定的目标单词。暴力搜索所有可能的状态，target可根据每个字符是否已满足拆成2^N个不同的组合/状态，再看达成该状态需要最小的sticker数。遍历所有的状态，初始状态是target内字符全不满足，终结状态是全部都满足，依次对每个状态检查用所有stickers更新后形成的新状态是否是新状态的最优解。和一般DP的区别在于这里不是用过去的状态求当前状态最优解，而是用当前状态去更新它下一步action后对应的状态。一共2^N个状态，典型的bitmap应用，bit每一位的值表示对应字符是否已经被满足。

/*
 * @lc app=leetcode id=691 lang=cpp
 *
 * [691] Stickers to Spell Word
 */

// @lc code=start
class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
       const int N = target.size(), M = 1 << N; // bitmap
       vector<uint> dp(M, -1);
       dp[0] = 0;
       for (int i = 0; i < M; ++i) {
           if (dp[i] == -1) continue;
           for (string &s : stickers) {
               int next = i;
               for (const auto c : s) {
                   for (int j = 0; j < N; ++j) {
                       if ((next >> j & 1) == 0 && target[j] == c) {
                           next |= 1 << j;
                           break;
                       }
                   }
               }
               dp[next] = min(dp[next], dp[i] + 1);
           }
       }
       return dp[M - 1];
    }
};
// @lc code=end