题目描述
给一个列表ss，里面存的是不同的单词贴纸，单词只包含小写字母，可以把贴纸内的每个字母单独切割，
给一个目标t，当不限制每个贴纸使用次数时，问要拼出目标t需要的最小贴纸数？
f1-朴素动态规划+状态压缩
基本分析
- 看到t的长度不会超过15，想到怎么表达t的凑成状态？用s表示t的凑成状态，如果t[i]被凑成，在state中的低位为1，否则为0.举个例子，对于t='abcd', 当s=1时，表示t[0]被凑成，即使'a'被凑出来了
- 凑的其实状态和最终状态是啥？起始状态是0，凑成是(1<<n)-1
- 和dp建立连接时，怎么定义dp的状态？dp[s]表示当前t的凑成状态是s时，使用的最少贴纸数量
- 因为题目是最少次数，初始化状态和转移时注意什么？初始化时f[0]=0,其余状态初始化为inf；转移时，对新的状态ns，f[ns] = min(f[ns], f[s]+1)
- 考虑dp怎么进行转移？通过4层循环实现:
- (1)先是顺序的遍历s，从0到(1<<n)-1, 对不能转移的状态直接跳过
- (2)从贴纸中去遍历每个单词word，在遍历这个单词之前，未来状态ns初始化为s
- (3)遍历单词中每个字母c
- (4)遍历t中每个字母ch及对应的位置j。如果要转移需要满足条件：<1>c肯定是要等于ch，<2>未来状态ns在j位置需要是0。如果满足以上条件，表示能转移，把ns的对应j位置为1。如果不满足以上条件，去在t中找下一位继续。需要注意的是，当在t中找到合适的位置并且更新状态时，为什么要break？因为对于贴纸的某个字母c，只能利用1次，在题目设计中先按照顺序从高位到低位填充。
需要注意更新ns的状态的位置，是在遍历完某个单词之后，为什么？因为对于某个贴纸单词，（1）可能可以从当前状态s出发，填充t的多个位置，这个时候，s-ns就有多次更新;（2）也可能只有一个字母能用；（3）也可能没有一个字母能用。对于前两种情况，只多了一个单词，所以f[ns]=min(f[ns], f[s]+1)，对于后一种情况ns没有更新，前面的公式也能用。
- 最后的结果怎么考虑？当f[-1]非inf时，返回f[-1]
代码
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
n = len(stickers)
m = len(target)
mask = 1 << m
f = [inf] * mask
f[0] = 0
for s in range(0, mask):
if f[s] == inf:
continue
for word in stickers:
ns = s
for i, c in enumerate(word):
for j, ch in enumerate(target):
if ch == c and ((ns>>j) & 1 ==0):
ns |= 1<<j
break
f[ns] = min(f[ns], f[s]+1)
return f[-1] if f[-1] !=inf else -1
复杂度
时间：用m表示t的长度，n表示贴纸数组的长度，k表示单词的平均长度。状态个数是\(2^m\),单个状态的复杂度是\(O(n*k*m)\), 最终复杂度\(O(2^m*n*k*m)\)
空间：存dp状态需要\(O(2^m)\)
总结
- 通过t的长度情况看出来用状态压缩表示凑成情况。和之前不一样的是，这里是表示索引的凑成情况，对应到t中，s=1表示索引i=0凑出，也就是高位凑出
- 考虑怎么从凑出的状态定义dp状态，根据题意，顺理成章定义dp[s]为凑出状态为s时的使用的最少贴纸数
- 从dp状态定义初始化时，dp[0]=0是清楚的，因为涉及到最小，所以其他需要初始化为大值inf
- 考虑转移时，这里是枚举s，然后枚举某个单词word，看利用word把状态s更新为ns，最后更新f[ns]的值。这里有一些需要注意的点:(1)有可能枚举的s是不能转移的，这个时候continue；（2）枚举到某个单词word后，需要枚举单词的每个字母，这个字母能用也得满足条件<1>是t的j处需要的字母，<2>新状态ns中对应的j位是0，满足以上两个条件是，才继续更新ns。当某个单词的字母都遍历完以后，尝试更新s到ns的状态。
- 这里有个问题是，对每个状态s都要枚举所有单词，而有可能大部分单词都没有包含需要处理的字符。举个例子，假如ss=['abc','d', 'xyzd'], t='dax', 对于状态s=0，我发现需要先找t[0]处的单词d,这个时候我就不用去遍历单词abc了，因为'abc'根本不包含我需要的字母'd'。所以有个优化的思路是预处理ss数组，得到一个哈希表mp，用来存需要字母对应的单词索引。
f2-预处理优化+动态规划+状态压缩
基本分析
- 其他和上面类似，怎么去建立这个哈希表？遍历ss，获取每个单词索引i和单词word，再遍历单词的每个字母c，建立c到单词索引的关系mp，这里需要考虑去重，例如某个单词有两个相同的字母，只记一次单词索引就行
- 怎么利用上面的哈希表mp来优化算法？还是4重循环，只是第2层少了
- （1）还是遍历状态s，这里需要<1>s中不能转移的pass; <2>从低位开始，找到s中第一个非1的位置loc，利用loc找到需要凑的字母，利用字母找到需要遍历的单词索引的列表
- （2）遍历这个列表索引，可以保证每个单词都包含要填充的字符
- （3）第3层和之前类似
- （4）第4层和之前类似
代码
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
n = len(stickers)
m = len(target)
mask = 1 << m
f = [inf] * mask
f[0] = 0
mp = dict()
# 统计字母对应的单词
for i, word in enumerate(stickers):
for c in word:
if not c in mp:
mp[c] = []
if not i in mp[c]:
mp[c].append(i)
for s in range(mask):
if f[s] == inf:
continue
loc = -1
for i in range(m):
if loc != -1:
break
if (((s>>i)&1)==0):
loc = i
if loc == -1:
continue
idx = target[loc]
ls = mp.get(idx, [])
for i in range(len(ls)):
word = stickers[ls[i]]
ns = s
for j, c in enumerate(word):
for k, ch in enumerate(target):
if ch == c and (((ns>>k)&1)==0):
ns |= (1<<k)
break
f[ns] = min(f[ns], f[s]+1)
return f[-1] if f[-1] != inf else -1
复杂度
时间：\(O(2^m*n*k*m)\)最差情况第2层也是\(O(n)\),和上面一样，但是平均下来要少。
空间：\(O(2^m)\)
总结
- 建立字母对应的单词索引列表时，注意去重
- 利用预处理的mp优化第2层循环时，需要先找到要填哪个字母（从低到高第一个非1），在利用字母从mp中去查到索引列表，后面对列表遍历就行。