我直接给你 可提交 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 版本吗?

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐