LeetCode 518. 零钱兑换 II — Java 实现题目思路这是典型的完全背包问题· 硬币可以无限次使用· 求组合数不关心顺序· 与 322 题零钱兑换的区别322 求的是最少硬币数本题求的是方案总数核心代码一维 DP推荐classSolution{publicintchange(intamount,int[]coins){// dp[j] 表示凑成金额 j 的组合数int[]dpnewint[amount1];dp[0]1;// 凑成金额 0 只有一种方案什么都不选// 外层遍历硬币内层遍历金额正序 组合数for(intcoin:coins){for(intjcoin;jamount;j){dp[j]dp[j-coin];}}returndp[amount];}}为什么外层必须遍历硬币这是本题最关键的要点循环顺序 含义 结果外层硬币 / 内层金额正序 每种硬币逐个加入不会重复计算顺序 ✅ 组合数外层金额 / 内层硬币 每个金额位置枚举所有硬币考虑排列 ❌ 排列数示例coins [1, 2, 5], amount 5· 正确答案组合数 4· 5· 2 2 1· 2 1 1 1· 1 1 1 1 1· 如果顺序颠倒排列数会得到 9 种把 2111 和 1112 都算作不同方案二维 DP 版本辅助理解classSolution{publicintchange(intamount,int[]coins){intncoins.length;// dp[i][j] 用前 i 种硬币凑成金额 j 的组合数int[][]dpnewint[n1][amount1];// 初始化凑成金额 0 的方案数为 1空集for(inti0;in;i)dp[i][0]1;for(inti1;in;i){for(intj1;jamount;j){// 不使用第 i 种硬币dp[i][j]dp[i-1][j];// 使用第 i 种硬币可以重复使用所以是 dp[i][j - coin] 而不是 dp[i-1][j - coin]if(jcoins[i-1]){dp[i][j]dp[i][j-coins[i-1]];}}}returndp[n][amount];}}观察dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i][j-coin]同一行的左侧因此可以压缩成一维——这就是推荐写法。复杂度分析· 时间复杂度O(n × amount)其中 n coins.length· 空间复杂度O(amount)边界情况情况 结果amount 0 1空方案coins []amount 0 0amount 无法凑出 0题目保证最终结果在 int 范围内不超过 2^31 - 1无需 long。
