贴纸拼词 —— 记忆化搜索 / 状压DP

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

题意
给定一个长度为 n 的字符串 S，给定 m 种字符串 a[]，每种字符串无限个。
现在要选出一些字符串，将其每个字符剪切后可以拼接成字符串 S。
问，最少要选多少个字符串？

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

思路
目标字符串长度很小，考虑记忆化搜索：

对于当前的字符串 s 来说，选择一个字符串 t，将 s 中能由字符串 t 剪切得到的位置删掉后得到新串，然后递归到这个新串。
如果当前串为空，说明到了终点，返回 0。
否则，返回 m 个新串到达终点的答案的最小值 + 1。

为了方便转移，可以将长度最大为 15 的串进行状态压缩，对于某一位来说如果是 1 说明没删，如果是 0 说明删掉了，状压成一个整数。

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++) //遍历所有位置，将能用串 i 删掉的位置都删掉
            {
                if(!(x >> j & 1)) continue;
                char c = aim[j];
                if(tcnt[c - 'a']) tcnt[c - 'a']--, tx -= 1<<j;
            }
            if(tx == x) continue; //如果串无变化不再递归当前值，否则会陷入循环
            if(!f[tx]) dfs(tx); //剪枝
            sum = min(sum, f[tx] + 1); //递归到新串
        }
        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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

按照这种思路同样可以用 bfs 来做，对于当前串能够通过选择一个操作串得到一个新串，操作次数为1，最终首次得到目标串的操作次数便是最小操作次数。

---

同样，可以转化为状压DP的做法。

遍历所有集合，对于当前集合来说，选择一种字符串删除若干元素来得到一个新的集合，用新集合状态 + 1 得到当前集合状态。

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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38