精選力扣500題 第65題 LeetCode 322. 零錢兌換【c++/java詳細題解】

1、題目

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

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

示例 1：

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

示例 2：

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

示例 3：

輸入：coins = [1], amount = 0
輸出：0

示例 4：

輸入：coins = [1], amount = 1
輸出：1

示例 5：

輸入：coins = [1], amount = 2
輸出：2

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 104

2、思路

(動態規劃，完全背包問題) O ( n m ) O(nm) O(nm)

完全背包問題，

相當于有n 種物品，每種物品的體積是硬幣面值，價值是1，每種物品可用無限次，問裝滿背包最少需要多少價值的物品？

先考慮二維狀態

狀態表示： f[i][j] 表示從前i種硬幣中選，且總金額恰好為j的所需要的最少硬幣數，

那么f[n][amount]就表示表示 從前n種硬幣中選，且總金額恰好為amount的所需要的最少硬幣數，即為答案，

集合劃分：

按照第i種硬幣可以選 0個,1個，2個，3個，，，，k個劃分集合 f[i][j]，其中k*w[i] <= j,也就是說在背包能裝下的情況下，列舉第i種硬幣可以選擇幾個，

不使用第i種硬幣，狀態表示: f[i-1][j]

使用第i種硬幣，假設我們使用k個(容量允許的情況下)，狀態表示：min(f[i-1][j - k*coin]) + k

狀態計算方程：

f[i][j] = min(f[i-1][j],f[i-1][j-coins[i]] + 1,f[i-1][j-2*coins[i]] + 2,......,f[i-1][j-k*coins[i]] + k) .

初始化條件:

f[0][0]=0，其余f[0][j] = INF，表示當沒有任何硬幣的時候，存在湊成總和為 0 的方案，方案所使用的硬幣為 0；湊成其他總和的方案不存在，

3、c++代碼

class Solution {
public:
    int INF = 1000000000;
    int coinChange(vector<int>& coins, int amount) {
         int n = coins.size();
         vector<vector<int>> f (n + 1, vector<int>(amount + 1, INF));

         f[0][0] = 0;   
         for(int i = 1; i <= n; i++)
         {
         	int val = coins[i-1];
            for(int j = 0; j <= amount; j++)
                for(int k = 0; k*val <= j; k++)
                {
                    f[i][j] = min(f[i][j] , f[i-1][j-k*val] + k);
                }
         }	 
        if (f[n][amount] == INF) f[n][amount] = -1;
        return f[n][amount];
    }
};

4、java代碼

class Solution {
    int INF = 1000000000;
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] f = new int[n + 1][amount + 1];

        for (int i = 0; i <= n; i++) 
            for(int j = 0; j <= amount; j++)
               f[i][j] = INF;
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            int val = coins[i - 1];
            for (int j = 0; j <= amount; j++) {
                for (int k = 0; k * val <= j; k++) {
                      f[i][j] = Math.min(f[i][j], f[i-1][j-k*val] + k);
                    }
                }
        }
        if (f[n][amount] == INF) f[n][amount] = -1;
        return f[n][amount];
    }
}

時間復雜度分析： 共有 n ? a m o u n t n * amount n?amount 個狀態需要轉移，每個狀態轉移最多遍歷 a m o u n t amount amount次，整體復雜度為 O ( n ? a m o u n t 2 ) O(n * amount^2) O(n?amount2)

超出時間限制，考慮一維優化，

5、一維優化

v代表第i件物品的體積(面值)

f[i][j] = min( f[i-1][j],f[i-1][j-v] + 1,f[i-1][j-2v] + 2......f[i-1][j-kv] + k)

f[i][j-v] + 1 = min(f[i-1,[j-v] + 1,f[i-1][j-2v] + 2......,f[i-1][j-kv] + k)

因此：

f[i][j] = min(f[i-1][j],f[i][j-v] + 1)

圖示：

去掉一維：

狀態計算方程為: f[j] = min([j],[j-v] + 1)

物品的體積即硬幣面值: f[j] = min([j],[j-coins[i]] + 1)

時間復雜度分析：令 n 表示硬幣種數，m 表示總價錢，則總共兩層回圈，所以時間復雜度是 O ( n m ) O(nm) O(nm)，

6、c++代碼2

class Solution {
public:

    int INF = 1000000000;

    int coinChange(vector<int>& coins, int amount) {
        vector<int> f(amount + 1, INF);
        f[0] = 0;
        for (int i = 0; i < coins.size(); i ++ )
            for (int j = coins[i]; j <= amount; j ++ )
                f[j] = min(f[j], f[j - coins[i]] + 1);
        if (f[amount] == INF) f[amount] = -1;
        return f[amount] ;
    }
};

7、java代碼2

public class Solution {
    int INF = 1000000000;
    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        Arrays.fill(f, max);
        f[0] = 0;
        for (int i = 0; i < coins.size(); i ++ )
            for (int j = coins[i]; j <= amount; j ++ )
                    f[i] = Math.min(f[i], f[i - coins[j]] + 1);
                }
            }
        }
        if (f[amount] == INF) f[amount] = -1;
        return f[amount] ;
    }
}

原題鏈接：322. 零錢兌換