Sticker Spelling - Memory Search / Shape Pressure DP

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

题意
给定一个长度为 n 的字符串 S,给定 m 种字符串 a[],An unlimited number of each type of string.
Now to pick out some strings,After each character is cut, it can be spliced ​​into a string S.
问,How many to choose at least个字符串？

$1\le n\le 15,1\le m\le 50,1\le |a_i|\le 10$

思路
The target string length is small,考虑记忆化搜索：

for the current string s 来说,选择一个字符串 t,将 s can be composed of strings t After the cut position is deleted, a new string is obtained,Then recurse to this new string.
If the current string is empty,The description comes to an end,返回 0.
否则,返回 m The minimum value of the answer for a new string to reach the end + 1.

为了方便转移,The maximum length can be 15 The string is state compressed,For someone if yes 1 Description not deleted,如果是 0 Description deleted,compressed into an integer.

class Solution {
    
public:
    string aim;
    int x, ans = 1e9;
    vector<string> st;
    int f[1<<15];
    int cnt[60][30];
    int tcnt[30];

    void pre()
    {
    
        for(int i=0;i<st.size();i++)
        {
    
            string s = st[i];
            for(char c : s) cnt[i][c-'a']++;
        }
    }

    int dfs(int x)
    {
    
        int sum = 1e9;
        if(x == 0) return 0;

        for(int i=0;i<st.size();i++)
        {
    
            for(int j=0;j<26;j++) tcnt[j] = cnt[i][j];
            
            int tx = x;
            for(int j=0;j<15;j++) //遍历所有位置,will be able to use strings i Deleted locations are deleted
            {
    
                if(!(x >> j & 1)) continue;
                char c = aim[j];
                if(tcnt[c - 'a']) tcnt[c - 'a']--, tx -= 1<<j;
            }
            if(tx == x) continue; //If there is no change in the string no longer recurses the current value,否则会陷入循环
            if(!f[tx]) dfs(tx); //剪枝
            sum = min(sum, f[tx] + 1); //Recursively to a new string
        }
        f[x] = sum; //记忆化
        return sum;
    }

    int minStickers(vector<string>& stickers, string target) {
    
        aim = target;
        st = stickers;
        pre();

        for(int i=0;i<target.size();i++) x += 1<<i;
        
        int ans = dfs(x);

        if(ans == 1e9) return -1;
        return ans;
    }
};

It can also be used in this way bfs 来做,A new string can be obtained by selecting an operation string for the current string,操作次数为1,The number of operations that finally obtains the target string for the first time is the minimum number of operations.

---

同样,Can be converted into shape pressureDP的做法.

遍历所有集合,for the current collection,Choose a string and delete several elements to get a new set,Use the new collection state + 1 Get the current collection state.

class Solution {
    
public:
    int cnt[60][30];
    int tcnt[30];
    int f[1<<15];

    int minStickers(vector<string>& stickers, string target) {
    
       for(int i=0;i<stickers.size();i++)
       {
    
            string s = stickers[i];
            for(char c : s)
                cnt[i][c - 'a'] ++;
       }

       int n = target.size();

       for(int i=0;i<1<<n;i++) f[i] = 1e9;
       f[0] = 0;
       for(int i=0;i<1<<n;i++)
       {
    
            int x = i;
            for(int j=0;j<stickers.size();j++)
            {
    
                int tx = x;
                for(int k=0;k<26;k++) tcnt[k] = cnt[j][k];

                for(int k=0;k<n;k++)
                {
    
                    if(!(x >> k & 1)) continue;
                    if(tcnt[target[k] - 'a']) tcnt[target[k] - 'a']--, tx -= 1<<k;
                }
                f[x] = min(f[x], f[tx] + 1);
            }
       }
        if(f[(1<<n) - 1] == 1e9) return -1;
        return f[(1<<n) - 1];
    }
};