两道经典 DP 题：零钱兑换 单词拆分（完全背包 + 字符串 DP）

前言在动态规划的进阶阶段有两道题是绕不开的《零钱兑换》和《单词拆分》。它们都用到了「完全背包」的思想一个是典型的数值类 DP一个是字符串类 DP掌握了它们你就能打通 DP 的一大半任督二脉。一、零钱兑换LeetCode 322题目描述给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。你可以认为每种硬币的数量是无限的。核心思路完全背包 DP这是一道典型的完全背包问题背包容量amount物品硬币面额每个可以无限次使用目标用最少的硬币数量装满背包状态定义dp[i]表示凑成金额i所需的最少硬币数。转移方程对于每个金额i遍历所有硬币面额coindp[i] min(dp[i], dp[i - coin] 1)边界条件dp[0] 0金额为 0 时需要 0 个硬币其余dp[i]初始化为无穷大表示暂时无法凑出代码实现Java 版java运行public class CoinChange { public int coinChange(int[] coins, int amount) { // dp[i] 凑成金额i的最少硬币数 int[] dp new int[amount 1]; // 初始化设置为无穷大 Arrays.fill(dp, amount 1); dp[0] 0; for (int i 1; i amount; i) { for (int coin : coins) { if (i coin) { dp[i] Math.min(dp[i], dp[i - coin] 1); } } } // 如果dp[amount]还是无穷大说明无法凑出 return dp[amount] amount ? -1 : dp[amount]; } public static void main(String[] args) { CoinChange solution new CoinChange(); int[] coins {1, 2, 5}; int amount 11; System.out.println(solution.coinChange(coins, amount)); // 输出3551 } }关键知识点时间复杂度O (amount × n)n 为硬币种类数空间复杂度O (amount)优化技巧硬币先排序遇到coin i可以提前 breakBFS 解法也可以实现第一次到达amount的层数就是最少硬币数。二、单词拆分LeetCode 139题目描述给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。核心思路字符串 DP 完全背包这道题是字符串类的完全背包问题背包容量字符串s的长度物品字典中的单词每个可以无限次使用目标判断能否用单词拼接出整个字符串状态定义dp[i]表示字符串s的前i个字符能否被字典中的单词拼接而成。转移方程对于每个位置i遍历所有j i如果dp[j] true且子串s[j:i]在字典中则dp[i] true。边界条件dp[0] true空字符串可以被拼接代码实现Java 版java运行import java.util.HashSet; import java.util.List; import java.util.Set; public class WordBreak { public boolean wordBreak(String s, ListString wordDict) { SetString wordSet new HashSet(wordDict); int n s.length(); boolean[] dp new boolean[n 1]; dp[0] true; // 空字符串可被拼接 for (int i 1; i n; i) { for (int j 0; j i; j) { if (dp[j] wordSet.contains(s.substring(j, i))) { dp[i] true; break; // 找到即可提前退出 } } } return dp[n]; } public static void main(String[] args) { WordBreak solution new WordBreak(); String s leetcode; ListString wordDict List.of(leet, code); System.out.println(solution.wordBreak(s, wordDict)); // 输出true } }关键知识点时间复杂度O (n²)n 为字符串长度内层遍历 j外层遍历 i空间复杂度O (n m)m 为字典单词数存储 Set优化技巧可以提前计算字典中单词的最大长度j 的遍历范围缩小到[i - maxLen, i)减少不必要的遍历。