322.-coin-change.md

322. Coin Change

{% tabs %} {% tab title="Python" %}

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        ## 首先来分析分析 
        ## 这题我们要求恰好为amount 时，硬币最少的个数
        
# f[i] = 这是多重背包， 正序遍历
        f = [float("inf")] * ( amount + 1 )
        f[0] = 0
        for c in coins:
            for i in range(1, amount + 1):
                if i >= c:
                    f[i] = min(f[i], f[i - c] + 1)
                    
        return f[amount] if f[amount] != float("inf") else - 1

{% endtab %}

{% tab title="C++" %}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount + 1);
        dp[0] = 0; // 初始化
        for (int i = 1; i <=amount; i++){
            for (int c:coins ){
                if (i < c){
                    continue;
                }
                dp[i] = min(dp[i], 1 + dp[i - c]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
};

{% endtab %} {% endtabs %}