322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

題解：

輸入不同面值的鈔票 coin 和金額 amount，用最少的數量的鈔票組成金額 amount，輸出可以使用的最少鈔票數量；如果無法組成該金額，輸出 -1；
如果coins = [1, 2, 5]，想要組成金額 amount，有三種可能：

1. 金額 amount - 1 加上一張1元鈔票；
2. 金額 amount - 2 加上一張2元鈔票；
3. 金額 amount - 5 加上一張5元鈔票；

想到這，我們已經能到狀態(tài)轉移方程了：
dp[i] 表示組成金額 i 需要的鈔票數，則dp[amount] = min(dp[amount-1], dp[amount-2], dp[amount-5]) + 1；

依然對于coins = [1, 2, 5] 來說：
原問題：組成金額 n 的最少鈔票數；
子問題：
dp[1] = 1；
dp[2] = 1；
dp[3] = min(dp[1], dp[2]) + 1：金額3可能有dp[3-1]和dp[3-2]兩種可能；
dp[4] = min(dp[2], dp[3]) + 1：金額4可能有dp[4-1]和dp[4-2]兩種可能；
dp[5] = 1；
動態(tài)規(guī)劃狀態(tài)轉移方程：
dp[amount] = min(dp[amount-1], dp[amount-2], dp[amount-5]) + 1；
邊界狀態(tài)：
對于coins = [1, 2, 5] 來說：dp[1] = 1；dp[2] = 1；dp[5] = 1；
如果鈔票不能組成金額呢？比如coins = [2, 5]，amount = 6；
其實很好解決，題目要求不能組成時輸出 -1，那么我們只需要事先將 dp 的所有值初始化為 -1就可以了；

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    //vector<int> coinChange(vector<int> &coin, int amount) {
    int coinChange(vector<int> &coin, int amount) {
        //if (amount == 0) {
            //return 0;
        //}
        vector<int> dp(amount + 3, -1);
        dp[0] = 0;
        for (int i = 0; i <= amount; i++) {
            for (int j = 0; j < coin.size(); j++) {
                //if (i < coin[j]) {
                //  break;
                //}
                //if (i == coin[j]) {
                    //dp[i] = 1;
                //}
                if (i >= coin[j] && dp[i - coin[j]] != -1) {
                    //if (dp[i] == -1) {
                        //dp[i] = dp[i - coin[j]] + 1;
                    //}
                    //else {
                    if (dp[i] == -1 || dp[i] > dp[i - coin[j]] + 1) {
                        dp[i] = dp[i - coin[j]] + 1;
                    }
                    //}
                }
            }
        }
        //return dp;
        return dp[amount];
    }
};

int main() {
    vector<int> coin;
    coin.push_back(1);
    coin.push_back(2);
    coin.push_back(5);
    coin.push_back(10);
    coin.push_back(7);
    Solution s;
    //vector<int> dp;
    //dp = s.coinChange(coin, 14);
    //for (int i = 0; i < dp.size(); i++) {
    //  printf("%d ", dp[i]);
    //}
    printf("金額 14 可以使用的最少鈔票數量：%d", s.coinChange(coin, 14));
    return 0;
}

結果

金額 14 可以使用的最少鈔票數量：2

My Solution(Python)

class Solution:
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [-1 for i in range(amount + 1)]
        dp[0] = 0
        # dp[i] = min(dp[i-1], dp[i-2], dp[i-5], dp[i-7], dp[i-10])
        for i in range(1, amount + 1):
            for mark_coin in range(len(coins)):
                if i - coins[mark_coin] >= 0 and dp[i-coins[mark_coin]] != -1:
                    if dp[i] == -1 or dp[i] > dp[i-coins[mark_coin]] + 1:
                        dp[i] = dp[i-coins[mark_coin]] + 1        
        return dp[amount]

Reference:

class Solution:
    result = -1
                
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if amount == 0:
            return 0
        N = len(coins)
        coins.sort()
        self.result = amount + 1
        
        def dp(coins, idx, remain, cnt, checked=False):
            if cnt >= self.result:
                return False

            if not checked:
                q = remain // coins[idx]
                if remain % coins[idx] == 0:
                    self.result = min(self.result, cnt + q)
                    return True
                elif cnt + q + 1 >= self.result:
                    return False

            if idx > 0:
                if coins[idx] < remain:
                    dp(coins, idx, remain - coins[idx], cnt + 1, True)
                dp(coins, idx-1, remain, cnt)

        dp(coins, N-1, amount, 0)

        if self.result <= amount:
            return self.result
        else:
            return -1