[Leedcode][JAVA][面試題 08.11][硬币][動态規劃]

【問題描述】 面試題 08.11.硬币

硬币。給定數量不限的硬币，币值為25分、10分、5分和1分，編寫代碼計算n分有幾種表示法。(結果可能會很大，你需要将結果模上1000000007)

示例1:

 輸入: n = 5
 輸出：2
 解釋: 有兩種方式可以湊成總金額:
5=5
5=1+1+1+1+1

           

【解答思路】

1. 動态規劃 二維數組

1.1 令 dp[i][j] 為周遊到當下這個硬币時，組成金額 j 的方法數目

1.2 有兩種可能性

（1）目前這個硬币沒有取，dp[i][j]=dp[i-1][j]；

（2）目前這個硬币取了，dp[i][j]=dp[i][j-coins[i]]。最後的結果是兩者的和

1.3 将狀态轉移方程翻譯成代碼，并處理邊界條件

時間複雜度：O(NM) 空間複雜度：O(NM)

N ：金額 M：硬币類型

class Solution {
    public int waysToChange(int n) {

        if (n < 5)
            return 1;
        if (n == 5)
            return 2;
        int[] coins = {1, 5, 10, 25};
        int[][] dp = new int[4][n + 1];
        // 當數量為0，1時，有1種表示法
        for(int i = 0; i < 4; ++i){
             dp[i][0] = 1;
             dp[i][1] = 1;
        }  
        // 當隻有一種硬币時，隻有1種表示法
        for(int i = 0; i <=n; ++i)
            dp[0][i] = 1;
        /*
         * 狀态：dp[i][j]表示[0...i]種硬币能組合為j的所有不同種數
         * 狀态轉移：取 或 不取 目前硬币coins[i]
         */
        for (int i = 1; i < 4; ++i) {
            for (int j = 2; j <= n; ++j) {
                if (j >= coins[i])
                    dp[i][j] = (dp[i][j - coins[i]] + dp[i - 1][j]) % 1000000007;
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[3][n];
    }
}


           

2. 動态規劃優化 一維數組

從上面的狀态轉移方程可以看出，dp[i][j]隻與dp[i-1][j]和dp[i][j-coins[i]]有關，是以完全可以把第一個次元除掉，隻用一個一維數組存儲

時間複雜度：O(MN) 空間複雜度：O(N)

N ：金額 M：硬币類型

public int waysToChange2(int n) {
    int[] dp=new int[n+1];
    int[] coins={1,5,10,25};

    for(int i=0;i<=n;i++)
        dp[i]=1;
    
    for(int i=1;i<4;i++){
        for(int j=1;j<=n;j++){
            if(j>=coins[i])
                dp[j]=(dp[j]+dp[j-coins[i]])%1000000007;
        }
    }
    return dp[n];
}


           

【總結】

1. 動态規劃流程

第 1 步：設計狀态

第 2 步：狀态轉移方程

第 3 步：考慮初始化

第 4 步：考慮輸出

第 5 步：考慮是否可以狀态壓縮

2. 數組初始化

• 一維數組

1.在定義時初始化。

int[] arrays = {1, 2, 3, 4, 5};                    //簡化
	int[] arrays = new int[]{1, 2, 3, 4, 5};      //完整格式 推薦
           

2.先定空間，随後指派。

- int []age = new int[10];

       //動态初始化

       for (int i = 0; i < age.length; i++) {
           age[i] = i;}
           

• 二維數組

1.在定義時初始化。

double[][] a = new double[][] {{1,2,3},{4,2,7}};
double[][] b = new double[][] {{3,3},{1,1},{2,2}};

2.先定空間，随後指派。
           

double [][] container = new double[3][4];

for(int i = 0; i < 3;i++) {

for(int j = 0; j < 4;j++) {

container[i][j] = 4.5;

}

}

3.DFS 全排思想（順序有關） 不可以 無序方案

• n = 6 時 ，輸出次數3（實際2）
• 1 1 1 1 1 1
• 5 1
• 1 5（重複）

private int[] money = new int[]{1,5,10,25};  
    private int count = 0;
    public int waysToChange(int n) {
        if(n<5){
            return 1;
        }
        int i=0;
       
        conutSort(i,n);

        return  count;
    }

    void conutSort(int i,int n){
        if(i>n){
            return ;
        }
        if(i==n){
            count++;
            count = count % 1000000007;
        }
        if(i <n){
            for(int j= 0 ;j<4;j++){
                conutSort( money[j]+i, n);
            }
        }
    
    }
           

參考連結：https://leetcode-cn.com/problems/coin-lcci/solution/dong-tai-gui-hua-jian-dan-yi-dong-by-yuanninesuns/