難度：中等
頻次：52

題目：

給你一個整數(shù)數(shù)組 coins ，表示不同面額的硬幣；以及一個整數(shù) amount ，表示總金額。

計算并返回可以湊成總金額所需的 最少的硬幣個數(shù) 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認為每種硬幣的數(shù)量是無限的。

解題思路：完全背包的最小值問題

注意：背包問題的解析

• 查看背包類型
  • 0-1 背包 : 背包里的元素只能用一次
    • 先背包循環(huán)，后target循環(huán)（倒序），且target>num[i]
  • 完全背包 : 背包里的元素能夠重復(fù)利用
    • 先背包循環(huán)，后target循環(huán)（順序），且target>num[i]
  • 組合背包：背包中的物品要考慮順序
    • 先target循環(huán)，后背包循環(huán)（順序），且target>num[i]
  • 分組背包：多個背包，需要遍歷多個背包
    • 外循環(huán)背包，內(nèi)循環(huán)在根據(jù)題目轉(zhuǎn)化成上面三種背包的模板
• 問題類型
  • 求最值
    • 最大值 dp[i]=max{dp[i],dp[i-nums]+1}或dp[i]=max{dp[i],dp[i-num]+nums}
    • 最小值 dp[i]=min{dp[i],dp[i-nums]+1}或dp[i]=min{dp[i],dp[i-num]+nums}
  • 求存在問題
    • （bool） dp[i]=dp[i]||dp[i-num]
  • 求組合問題
    • dp[i]=dp[i]+dp[i-num]

代碼

class Solution {public int coinChange(int[] coins, int amount) {int[] dp=new int[amount+1];Arrays.fill(dp,amount+1);dp[0]=0;//完全背包：先背包循環(huán)、后目標(biāo)循環(huán)且正序,coin<=targetfor(int coin:coins){for(int i=0;i<=amount;i++){if(i>=coin){//最小值，dp狀態(tài)轉(zhuǎn)移方程固定dp[i]=Math.min(dp[i],dp[i-coin]+1);}}}return dp[amount]>amount?-1:dp[amount];} }

總結(jié)

以上是生活随笔為你收集整理的322. 零钱兑换的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。