LeetCode 518：零钱兑换 II（Coin Change II）—— 题解 ✅

LeetCode 518零钱兑换 IICoin Change II—— 题解 ✅ 内容概要给定不同面额的硬币coins和一个总金额amount计算凑成总金额的组合数每种硬币无限使用。✅ 完全背包✅ 组合问题不计顺序✅ 遍历顺序极其关键 解题思路一、问题本质硬币数量无限只关心金额是否凑成只统计组合数不计顺序 典型的完全背包组合计数二、DP 定义dp[j]凑成金额 j 的组合数三、状态转移方程dp[j]dp[j-coins[i]]含义使用当前硬币coins[i]新增的组合数 凑成j - coins[i]的方法数 核心重点遍历顺序✅ 正确的遍历顺序本题for(inti0;icoins.length;i){// 物品for(intjcoins[i];jamount;j){// 背包dp[j]dp[j-coins[i]];}}为什么这样写层级含义外层i枚举硬币种类内层j枚举金额✅保证硬币按顺序使用✅不会出现12和21重复✅ 得到的是组合数❌ 错误的遍历顺序for(intj0;jamount;j){for(inti0;icoins.length;i){dp[j]dp[j-coins[i]];}}❌ 会统计排列数❌12和21被视为不同方案 记忆口诀求组合数先物品后背包求排列数先背包后物品✅ AC 代码JavaclassSolution{publicintchange(intamount,int[]coins){int[]dpnewint[amount1];dp[0]1;// 凑成金额 0 有 1 种方式// 先遍历硬币物品for(inti0;icoins.length;i){// 再遍历金额背包for(intjcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}returndp[amount];}}⏱️ 复杂度分析指标复杂度时间复杂度O(coins.length × amount)空间复杂度O(amount)✅ 一句话总结完全背包 组合计数 外层硬币、内层金额正序遍历。