豆包 LeetCode 691.贴纸拼词 public int minStickers(String[] stickers, String target)
状态压缩 DP + 剪枝,这题标准做法就是用二进制表示 target 已拼成的状态。需要我给你讲每一行、或者改成记忆化搜索 DFS 版本吗?你直接复制提交就能过 LeetCode 691。
·
我直接给你 可提交 LeetCode 的 Java 版最优解:
状态压缩 DP + 剪枝,这题标准做法就是用二进制表示 target 已拼成的状态。
java
import java.util.*;
class Solution {
public int minStickers(String[] stickers, String target) {
int n = target.length();
int full = (1 << n) - 1;
int[] dp = new int[1 << n];
Arrays.fill(dp, -1);
dp[0] = 0;
// 预处理每个贴纸的字符计数
int[][] cnt = new int[stickers.length][26];
for (int i = 0; i < stickers.length; i++) {
for (char c : stickers[i].toCharArray()) {
cnt[i][c - 'a']++;
}
}
// BFS 式 DP(保证最先到 full 就是最小步数)
Queue<Integer> q = new LinkedList<>();
q.offer(0);
while (!q.isEmpty()) {
int mask = q.poll();
if (mask == full) return dp[mask];
for (int[] s : cnt) {
int[] tmp = s.clone();
int next = mask;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) continue; // 已经拼好了
char c = target.charAt(i);
if (tmp[c - 'a'] > 0) {
tmp[c - 'a']--;
next |= (1 << i);
}
}
if (next == mask) continue; // 这个贴纸没用
if (dp[next] == -1) {
dp[next] = dp[mask] + 1;
q.offer(next);
}
}
}
return -1;
}
}
思路极简版
- mask:二进制第 i 位 = 1 表示 target 第 i 个字母已拼好
- dp[mask]:拼到这个状态最少用多少贴纸
- 对每个状态,遍历所有贴纸,贪心把能补的字母都补上,得到新状态
- 用 BFS 保证第一次到达全 1 就是最小步数
你直接复制提交就能过 LeetCode 691。
需要我给你讲每一行、或者改成记忆化搜索 DFS 版本吗?
更多推荐




所有评论(0)