# 0691. Stickers to Spell Word
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/stickers-to-spell-word/
## 思路
状态压缩+背包问题
设置状态数组```dp[i]```,dp的大小是 ```N = 2^n```, dp的索引i的每一个bit表示的是```target```对应位置的字符是否得到了满足。举个例子，n=3时，i=3 (即011)表示```target```的末两位的字符得到了满足，但第一位的字符还没有得到满足。```dp[i]```表示在状态i下，需要的```sticker```的最少数目。

注意：这种状态的排列有一个非常好的性质。任何状态，只可能由位于其前面的状态转移得到，不可能从后面的状态转移得到。比如```i=3```(即 011)这个状态，只可能从```i=0,1,2```转移过来（通过使用某些合适的```sticker```）；再比如```i=4```(即100)这个状态，只可能从```i=0```转移过来。这种状态转移的性质，非常适合dp根据i从前往后的遍历。

所以，dp的大循环就是 ```for (state=0; state<(1<<n); state++)```. 对于该状态```state```，我们尝试每一个```sticker[k]```，计算状态```i```经过```sticker[k]```的帮助后得到的状态```new_state```（注意已经分析过```new_state```肯定是大于```state```的），那么```dp[new_state]```就可以得到更新```dp[new_state]=min(dp[new_state], dp[state]+1)```
## Code

class Solution {
    public int minStickers(String[] stickers, String target) {
        int n = target.length();
        int[] dp = new int[1<<n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int state=0; state<(1<<n); state++){
            for(String sticker:stickers){
                if(dp[state]==Integer.MAX_VALUE) continue;
                int nextState = getNext(sticker, target, state);
                dp[nextState] = Math.min(dp[nextState], dp[state]+1);
            }
        }
        return dp[(1<<n)-1]==Integer.MAX_VALUE?-1:dp[(1<<n)-1];
    }
    private int getNext(String sticker, String target, int curr){
        for(int i=0; i<sticker.length(); i++){
            char c = sticker.charAt(i);
            for(int j=0; j<target.length(); j++){
                if(target.charAt(j)==c && ((curr>>j)&1)==0){
                    curr += 1<<j;
                    break;
                }
            }
        }
        return curr;
    }
}