力扣热门100题之零钱兑换

张开发
• 2026/4/16 10:40:36 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

力扣热门100题之零钱兑换
核心思路dp[i]凑成金额i最少需要多少硬币转移dp[i] min(dp[i], dp[i - coin] 1)凑不出来就记为无穷大最后返回-1通俗解释1. 初始化dp[0] 0;凑 0 元需要 0 个硬币。其他dp[i]先设为amount1表示暂时凑不出来2. 状态转移for (每个金额 i) { for (每个硬币 coin) { if (coin 能用) { // 不选 coin保持 dp[i] // 选 coindp[i - coin] 1 dp[i] 最小的那个 } } }意思就是要凑 i 元可以在 i - coin 的基础上再加一枚 coin3. 结果判断return dp[amount] amount ? -1 : dp[amount];如果还是很大 → 凑不出来 → 返回 -1否则就是最少硬币数完整代码实现class Solution { public int coinChange(int[] coins, int amount) { int[] dp new int[amount 1]; // 初始化一个比最大可能还大的值 for(int i 1;iamount;i){ dp[i] amount 1; } dp[0] 0; for(int i 1;iamount;i){ for(int coin : coins){ if(coin i){ dp[i] Math.min(dp[i],dp[i -coin] 1); } } } return dp[amount] amount ? -1 : dp[amount]; } }

更多文章