Leetcode-322Coin Change

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元钞票；

想到这，我们已经能到状态转移方程了：
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；
动态规划状态转移方程：
dp[amount] = min(dp[amount-1], dp[amount-2], dp[amount-5]) + 1；
边界状态：
对于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