05 August 2008
给一个字符串数组，数组里面每个字符串可以用无数次，并且每个字符串中的字符可以重排，求组成目标字符至少需要多少个字符串
背包问题（变形）
给定物品的特点
给定背包的限制
求最小的物品的数量。
【位图法】因为待匹配串target的数量最多是15个，因此其子集的数量最多有 2^15个，而int类型占用四个字节，能够容纳标识所有target的子集。所以我们可以将target的子集 映射到 int的整型数中。
【int 与 target子集之间的映射关系】将int类型分解为二进制的形式后，有些位置为0，有些位置为1.表明在target中哪些位置的字符是否保留（1表示保留）。
【动态规划】dp中存储的是得到子集i,需要的最少的单词的数量。
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
class Solution {
public int minStickers(String[] stickers, String target) {
int n = target.length(), m = 1 << n; // if target has n chars, there will be m=2^n-1 subset of characters in target
int[] dp = new int[m];
for (int i = 0; i < m; i++) {
dp[i] = Integer.MAX_VALUE; // use index 0 - 2^n-1 as bitmaps to represent each subset of all chars in target
}
dp[0] = 0; // first thing we know is : dp[empty set] requires 0 stickers,
for (int i = 0; i < m; i++) {// for every subset i, start from 000...000。（起点这里很重要，因为大的集合往往依赖于小的集合）
if (dp[i] == Integer.MAX_VALUE) {
continue;
}
for (String s : stickers) { // try use each sticker as an char provider to populate 1 of its superset, to do that:
int sup = i;//关键代码（下面：在i上面加入一个单词后的效果）
for (char c : s.toCharArray()) {// for each char in the sticker, try apply it on a missing char in the subset of target
for (int r = 0; r < n; r++) {
if (target.charAt(r) == c && ((sup >> r) & 1) == 0) { //如果target中包含字符c , 并且sup中相应位置没有c。
sup |= 1 << r; //在sup中相应位置，加入c，形成新的集合。
break;
}
}
}
// after you apply all possible chars in a sticker, you get an superset that take 1 extra sticker than subset
// would take, so you can try to update the superset's minsticker number with dp[sub]+1;
dp[sup] = Math.min(dp[sup], dp[i] + 1);//判断是否需要替换原来sup中的值。
}
}
return dp[m - 1] != Integer.MAX_VALUE ? dp[m - 1] : -1;
}
}