零錢兌換問題

作者：Grey

原文地址:

部落格園：零錢兌換問題

CSDN：零錢兌換問題

題目描述

給你一個整數陣列 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。

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

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

題目連結：LeetCode 322. Coin Change

暴力遞迴

定義遞迴函數

int p(int[] coins, int i, int rest)

遞迴含義是：從 i 往後自由選擇，可以湊成 rest 的最少硬幣個數是多少。

所以主函數只需要呼叫p(coins, 0, amount)就是答案。

接下來看遞迴方法的實現：

首先是 base case ，有如下三種情況

情況1，如果rest < 0，說明之前的決策有問題（如果決策沒問題，不可能讓 rest 小於0）。返回 -1，表示決策有問題；

情況2，如果rest == 0，說明之前的決策湊出了 amount，接下來不需要任何硬幣，直接返回 0。

情況3，如果rest > 0，而此時，i == coins.length，說明 i 走到了盡頭（沒有硬幣可選了），rest都不為空，直接返回 -1 即可。

接下來就是普遍情況，列舉每個位置硬幣的數量 num 情況下，後續的最優解是什麼，核心程式碼如下，關鍵就是 while 迴圈中的內容：

int min = Integer.MAX_VALUE;
        int num = 0;
        // 列舉每個位置的硬幣個數，從 0 開始....
        while (num * coins[i] <= rest) {
            // 解決後續的錢數
            int after = p(coins, i + 1, rest - num * coins[i]);
            if (after != -1) {
                min = Math.min(num + after, min);
            }
            num++;
        }
        return min == Integer.MAX_VALUE ? -1 : min;

暴力遞迴解法的完整程式碼如下：

    public static int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) {
            return -1;
        }
        return p(coins, 0, amount);
    }

    // 從i...往後自由選擇，湊成rest的最少的硬幣個數
    public static int p(int[] coins, int i, int rest) {
        if (rest < 0) {
            return -1;
        }
        if (rest == 0) {
            return 0;
        }
        // rest不為空
        if (i == coins.length) {
            // i 已經走到盡頭
            return -1;
        }
        // 既沒有到最後，也還有剩餘
        int min = Integer.MAX_VALUE;
        int num = 0;
        while (num * coins[i] <= rest) {
            int after = p(coins, i + 1, rest - num * coins[i]);
            if (after != -1) {
                min = Math.min(num + after, min);
            }
            num++;
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }

使用暴力解，LeetCode 直接超時

動態規劃

可以將上述的暴力遞迴解法改成動態規劃的解，定義一個二維陣列int[][] dp = new int[n + 1][amount + 1]，其中

dp[i][j]的含義就是硬幣從 i 開始自由選擇，一直到最後，能湊出 j 的硬幣數量是多少

顯然有

for (int i = 1; i < amount + 1; i++) {
            dp[n][i] = -1;
        }

即：無硬幣情況下，只要 i 不等於 0，都不可能有選擇，直接賦 -1。

接下來就是遞迴過程轉換成動態規劃的格子依賴，其中 while 迴圈就是列舉每個位置硬幣有 num 枚的時候，最優解法是什麼。

        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j < amount + 1; j++) {
                int min = Integer.MAX_VALUE;
                int num = 0;
                // 列舉行為，可以繼續優化
                while (num * coins[i] <= j) {
                    int after = dp[i + 1][j - num * coins[i]];
                    if (after != -1) {
                        min = Math.min(num + after, min);
                    }
                    num++;
                }
                dp[i][j] = (min == Integer.MAX_VALUE ? -1 : min);
            }
        }

完整程式碼如下

class Solution {
    public static int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) {
            return -1;
        }
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 1; i < amount + 1; i++) {
            dp[n][i] = -1;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j < amount + 1; j++) {
                int min = Integer.MAX_VALUE;
                int num = 0;
                // 列舉行為，可以繼續優化
                while (num * coins[i] <= j) {
                    int after = dp[i + 1][j - num * coins[i]];
                    if (after != -1) {
                        min = Math.min(num + after, min);
                    }
                    num++;
                }
                dp[i][j] = (min == Integer.MAX_VALUE ? -1 : min);
            }
        }
        return dp[0][amount];
    }
}

列舉優化

動態規劃解中，以下 while 迴圈

                int min = Integer.MAX_VALUE;
                int num = 0;
                // 列舉行為，可以繼續優化
                while (num * coins[i] <= j) {
                    int after = dp[i + 1][j - num * coins[i]];
                    if (after != -1) {
                        min = Math.min(num + after, min);
                    }
                    num++;
                }
                dp[i][j] = (min == Integer.MAX_VALUE ? -1 : min);

可以優化成如下形式

                dp[i][j] = dp[i + 1][j];
                if (j - coins[i] >= 0 && dp[i][j - coins[i]] != -1) {
                    if (dp[i][j] == -1) {
                        dp[i][j] = dp[i][j - coins[i]] + 1;
                    } else {
                        dp[i][j] = Math.min(dp[i][j - coins[i]] + 1, dp[i][j]);
                    }
                }

完整程式碼見

class Solution {
    public static int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) {
            return -1;
        }
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 1; i < amount + 1; i++) {
            dp[n][i] = -1;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j < amount + 1; j++) {
                dp[i][j] = dp[i + 1][j];
                if (j - coins[i] >= 0 && dp[i][j - coins[i]] != -1) {
                    if (dp[i][j] == -1) {
                        dp[i][j] = dp[i][j - coins[i]] + 1;
                    } else {
                        dp[i][j] = Math.min(dp[i][j - coins[i]] + 1, dp[i][j]);
                    }
                }
            }
        }
        return dp[0][amount];
    }
}

演演算法和資料結構筆記

零錢兌換問題

零錢兌換問題

題目描述

暴力遞迴

動態規劃

列舉優化

更多