LeetCode題組：第322題-零錢兌換

• 2020 年 4 月 11 日
• 筆記

1.題目

難度：中

給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

示例 1:

輸入: coins = [1, 2, 5], amount = 11 輸出: 3 解釋: 11 = 5 + 5 + 1

示例 2:

輸入: coins = [2], amount = 3 輸出: -1

說明：你可以認為每種硬幣的數量是無限的。

2.我的解答

思路：

• 看題目的問法，只問最優值是多少，沒有要我們求最優解，可以通過動態規劃來解決這個問題；
• 最優子結構其實比較明顯，根據示例 1：

輸入: coins = [1, 2, 5], amount = 11

湊成面值為 11 的最小硬幣數可以由以下 3 者的最小值得到：

1、湊成面值為 10 的最小硬幣數 + 面值為 1的這一枚硬幣； 2、湊成面值為 9 的最小硬幣數 + 面值為 2 的這一枚硬幣； 3、湊成面值為 6 的最小硬幣數 + 面值為 5 的這一枚硬幣；

即：dp[11] = min (dp[10] + 1, dp[9] + 1, dp[6] + 1)。

可以直接把題目的問法設計成狀態。

第 1 步：定義「狀態」

dp[i]：湊齊總價值i需要的最少硬幣數，狀態就是問的問題。

第 2 步：寫出「狀態轉移方程」

根據對具體例子的分析： dp[amount] = min(1 + dp[amount - coin[i]]) for i in [0, len - 1] if coin[i] <= amount

看到程式碼實現

//動態規劃  int coinChange(int* coins, int coinsSize, int amount){      int i,j;      int *dp=(int *)malloc(sizeof(int)*(amount+1));//dp[i]代表i金額最小的      memset(dp,-1,sizeof(int)*(amount+1));//初始化        //將硬幣值的大小當做dp數組的下標      for(i=0;i<coinsSize&&coins[i]<=amount;i++) dp[coins[i]]=1;      dp[0]=0;      for(i=0;i<=amount;i++)//狀態轉移方程      {          int number=amount+1;          //逐個比較i-coins[j]所需的最小硬幣數          for(j=0;j<coinsSize;j++)          {              //如果硬幣可用              if(i-coins[j]>=0&&dp[i-coins[j]]!=-1)                  number=dp[i-coins[j]]<number ? dp[i-coins[j]]+1 : number;          }          if(number!=amount+1) dp[i]=number;      }      return dp[amount];  }