2.零錢兌換

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

-1

。

示例 1:

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

示例 2:

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

說明:

你可以認為每種硬币的數量是無限的。

在刷動态規劃經典例題——數字三角形之前，我已嘗試解答這個問題。

用的是深度優先周遊+貪心，先拿完所有最大面額的硬币，剩下的錢從剩下的硬币中一一選取

這樣算耗時大，還算不對。

了解了動态規劃後，過了幾天又看到這題，才想起來可以用動态規劃

分析：

（1）步驟拆分：

因為n為整數，是以每個步驟找零內插補點為1元，即：

求兌換n元的最小硬币，可以先求兌換n-1元最少硬币數量

求兌換n-1元，要先求兌換n-2元

。。。

一路下去，可以拆分成如下：

1、兌換0元（為了友善，是以從0開始）最少硬币數量

2、兌換1元最少硬币數量

3、兌換2元最少硬币數量

。。。

n+1、兌換n元最少硬币數量

設數組dp[n],且 dp[i] 為兌換 i 元所用最少硬币數量（是以要從0開始，dp[0]是兌換0元的最少硬币數量，多麼直覺啊）

（2）狀态轉移方程分析：

每一步找零內插補點為1，硬币面額為整且不小于1，設dp[0]=0（原因見示例分析）；

如果i元可以找零，那麼一定有   

找零i元 = 找零j元 + 一枚m元硬币   （j<i，j元可以找零 , m 屬于數組coins）

比如 ： 找零5元 等于 找零3元 + 一枚2元硬币

            找零5元 等于 找零5元 + 一枚5元硬币

設int b為該方案找零硬币數

則 b = dp[j]+1 （1表示1枚硬币）

當然滿足 i =j+m 的j和m很多，b也很多，

周遊0~i-1裡面可以找零的及數組coins，找出這樣的 j 和 m ，求出所有的b

我們選出最小的b作為最優解dp[i]即可

若一個j和m也沒有，記為-1，表示實在無法找零

狀态轉移方程不言而喻

（3）示例分析：

假設硬币面額數組c[3]={2,3,5},找零11元

找零 i 元 = 找零 j 元 +1枚m面額硬币 簡寫為：

z[i]=z[j]+m;

int b=某方案找零硬币個數，

dp[i]=找零 i 元最少硬币數量

硬币面額數組 c[3]={2,3,5}, 找零11元

1.找零0元：不存在的，∴dp[0]=0;

2.找零1元：還是不存在，∴dp[1]=0;

    但是題目要求不存在的話輸出-1，是以把dp[1]記為-1

3.找零2元：

    （1）找零0元+1枚2元硬币：找零方案f1=dp[0]+1(1表示1枚2元硬币！),f1=1

     沒有其他找零方法了，∴dp[2]=f1=1;

    （找零1元+1枚1元硬币？不存在的）

4.找零3元：

    （1）找零0元+1枚3元硬币：f1=dp[0]+1(1的意義同上！),f1=1

     沒有其他找零方案了，∴p[3]=f1=1;

    （找零2元+1枚1元硬币？找零2元的方案倒是有，但沒有1元硬币啊）

5.找零4元：

    （1）找零2元+1枚2元硬币：f1=dp[2]+1=2

    沒有其他方案了，是以dp[4]=f1=2

6.找零5元：
   
    （1）找零2元+1枚3元硬币：f1=dp[2]+1=2

    （2）找零3元+1枚2元硬币：f2=dp[3]+1=2

    （3）找零0元+1枚5元硬币：f3=dp[0]+1=1;
  
    ∴dp[5]=min(f1,f2,f3)=1

7.找零6元：

    （1）找零3元+1枚3元硬币：f1=dp[3]+1=2

    （2）找零4元+1枚2元硬币：f2=dp[4]+1=3

    ∴dp[6]=min(f1,f2)=2

8.找零7元：

    （1）找零4元+1枚3元硬币：f1=dp[4]+1=3

    （2）找零5元+1枚2元硬币：f2=dp[5]+1=2

    ∴dp[7]=min(f1,f2)=2

9.找零8元：

    （1）找零3元+1枚5元硬币：f1=dp[3]+1=2

    （2）找零6元+1枚2元硬币：f2=dp[6]+1=3

    ∴dp[8]=min(f1,f2)=2

10.找零9元：

    （1）找零4元+1枚5元硬币：f1=dp[4]+1=3

    （2）找零6元+1枚3元硬币：f2=dp[6]+1=3

    （3）找零7元+1枚2元硬币：f3=dp[7]+1=3

    ∴dp[9]=min(f1,f2,f3)=3

11.找零10元：

    （1）找零5元+1枚5元硬币：f1=dp[5]+1=2

    （2）找零7元+1枚3元硬币：f2=dp[7]+1=3

    （3）找零8元+1枚2元硬币：f3=dp[8]+1=3

    ∴dp[10]=min(f1,f2,f3)=2

12.找零11元(最終解)：

    （1）找零6元+1枚5元硬币：f1=dp[6]+1=3

    （2）找零8元+1枚3元硬币：f2=dp[8]+1=3

    （3）找零9元+1枚2元硬币：f3=dp[9]+1=4

    ∴dp[11]=min(f1,f2,f3)=3
           

是以找零11元最少要3個硬币

改造一下還能求出是哪三個硬币

本題代碼

class Solution {
    public int coinChange(int[] coins, int amount) {//硬币數組，找零面額
        if(amount==0){
            return 0;
        }
        
        int len=coins.length;
        int []dp=new int[amount+1];
        dp[0]=0;
        for(int i=1;i<=amount;++i){
            int h=amount;
            for(int j=0;j<len;++j){
                if(coins[j]<=i && dp[i-coins[j]]!=-1){
                    if(dp[i-coins[j]]<=h){
                        h=dp[i-coins[j]];
                    }                    
                }
            }
            if(h<i+1){
                dp[i]=h+1;
            }else{dp[i]=-1;}
        }
        return dp[amount];
    }
}