【Day 64 】2023-01-03 - 518. 零钱兑换 II

[azl397985856]

518. 零钱兑换 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/coin-change-2/

前置知识

暂无

题目描述

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:

输入: amount = 10, coins = [10]
输出: 1
 

注意:

你可以假设：

0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

[zjsuper]

class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [[0 for in range(amount+1)] for in range(len(coins))] for i in range(len(coins)): dp[i][0] = 1

    for i in range(0,len(coins)):
        for j in range(1,amount+1):
            if j-coins[i]>=0:
                dp[i][j] = dp[i-1][j]+dp[i][j-coins[i]]
            else:
                dp[i][j] = dp[i-1][j]

    return dp[-1][-1]

[Ryanbaiyansong]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        f = [0] * (amount + 1)
        # 完全背包求方案总数
        f[0] = 1
        for x in coins:
            for i in range(x, amount + 1):
                f[i] += f[i - x]

        return f[-1]

[heng518]

class Solution { public: int change(int amount, vector& coins) { vector dp(amount + 1, 0);

    dp[0] = 1;

    for(auto coin : coins)
        for(int i = coin; i <= amount; i++)
            dp[i] += dp[i-coin];

    return dp[amount];
}

};

[FlipN9]

/**
    TC: O(amount * N)   SC: O(amount)
*/
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                if (i - coin >= 0) {
                    dp[i] += dp[i - coin];
                }
            }
        }
        return dp[amount];
    }
}

[snmyj]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1);
        dp[0]=1;
        for(auto x:coins){
            for(int i=x;i<=amount;i++){
                dp[i]=dp[i-x]+dp[i];
            }
        }

        return dp[amount];
    }
};

[ringo1597]

java解题

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

[JancerWu]

class Solution {
    public int change(int amount, int[] coins) {
        int[] f = new int[amount + 1];
        f[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                f[i] += f[i-coin];
            }
        }
        return f[amount];

    }
}

[klspta]

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int coin : coins){
            for(int i = coin; i <= amount; i++){
                dp[i] += dp[i - coin]; 
            }
        }
        return dp[amount];
    }
}

[ApocKira]

int change(int amount, int[] coins) { int n = coins.length; int[] dp = new int[amount + 1]; dp[0] = 1; for (int i = 0; i < n; i++) for (int j = 1; j <= amount; j++) if (j - coins[i] >= 0) dp[j] = dp[j] + dp[j-coins[i]];

return dp[amount];

}

[bookyue]

code

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }

[zywang0]

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                if (i - coin >= 0) {
                    dp[i] += dp[i - coin];
                }
            }
        }
        return dp[amount];
    }
}

[yuxiangdev]

class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { for (int i = coin; i <= amount; i++) { if (i - coin >= 0) { dp[i] += dp[i - coin]; } } } return dp[amount]; } }

[chenming-cao]

解题思路

动态规划。此题为完全背包问题，因为硬币数量没有限制。用一维数组dp[i]表示达到amount = i的不同方法数。状态转移方程是dp[i] = dp[i] + dp[i - coin]，起始状态为dp[0] = 1，amount = 0是一个硬币也不取即可，此为1种方法。注意我们便利的时候i是从小到大遍历的，不会出现重复计算的情况。

代码

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        // base case: amount = 0, no coins selected, dp[0] = 1
        dp[0] = 1;
        for (int coin : coins) {
            // iterate i in increasing order, will not have repeated cases
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

复杂度分析

• 时间复杂度：O(n * amount), n为数组长度
• 空间复杂度：O(amount)

[Abby-xu]

思路

DP

代码

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount+1)
        dp[0] =1

        for i in range(len(coins)-1,-1,-1):
            for j in range(1,amount+1):
                if j - coins[i] >=0:
                    dp[j] += dp[j-coins[i]]

        return dp[amount] 

复杂度

...

[testplm]

var change = function (amount, coins) {
    let dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (let coin of coins) {
        for (let i = coin; i < amount + 1; i++) {

            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
};

[tiandao043]

思路

dp，二维的话定义状态 dp[i][j] 为使用前 i 个硬币组成金额 j 的组合数。

则有状态转移方程为：

dp[i][j] = dp[i-1][j] + dp[i][j - coins[i]]

其中 dp[i-1][j] 为不选择 coins[i] 的组合数， dp[i]j - coins[i]] 为选择 coins[i] 的组合数。

由于 dp[i][j] 仅仅依赖 dp[i-1][...] 因此使用滚动数组可以进行空间优化。优化后的转移方程为：

dp[i] = dp[i] + dp[i - coins[j]]

代码

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // vector<int> dp(amount+1);
        int n=coins.size();
        vector<vector<int>> dp(n+1, vector<int> (amount+1));
        // for(int i=0;i<=amount;i++){
        //     dp[0][i]=1;dp[i][0]=1;
        // }
        dp[0][0]=1;        
        for (int i = 1; i <= n; i++) {
            int val = coins[i - 1];
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = 1; k * val <= j; k++) {
                    dp[i][j] += dp[i - 1][j - k * val];  
                }
            }
        }

        return dp[n][amount];
    }
};

一维

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1);
        dp[0]=1;
        int n=coins.size();
        for(int i=0;i<n;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

O(m*n) O(m)

[yuexi001]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for (int& coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

[RestlessBreeze]

code

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for(auto x : coins){
            for(int i = x; i<=amount ;i++){
                dp[i]=dp[i - x] + dp[i];
            }
        }
        return dp[amount];
    }
};

[chiehw]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for(auto x : coins){
            for(int i = x; i<=amount ;i++){
                dp[i]=dp[i - x] + dp[i];
            }
        }
        return dp[amount];
    }
};

[buer1121]

class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0]*(amount + 1) dp[0] = 1

遍历物品

    for i in range(len(coins)):
        # 遍历背包
        for j in range(coins[i], amount + 1):
            dp[j] += dp[j - coins[i]]
    return dp[amount]

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        for(int i=0;i<n+1;i++){
            dp[i][0] = 1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=amount;j++){
                if(j-coins[i-1]>=0){
                    dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][amount];
    }
}

[mayloveless]

思路

完全背包问题，计数问题。对比零钱兑换1，初始化值为1，dp[i][j] = dp[i-1][j-c*coins[i]]

代码

var change = function(amount, coins) {
   let n = coins.length
    let dp = Array(n).fill().map(() => Array(amount+1).fill(0))
    for (let c = 0; c <= Math.floor(amount/coins[0]); ++c) {
        dp[0][c*coins[0]] = 1
    }
    for (let i = 1; i < n; ++i) {
        for (let j = 0; j <= amount; ++j) {
            let k = Math.floor(j/coins[i])
            for (let c = 0; c <= k; ++c) {
                dp[i][j] += dp[i-1][j-c*coins[i]]// 加总所有可能性
            } 
        }
    }
    return dp[n-1][amount]
};

复杂度

时间：O(namountk) 空间：O(n*amount)

[paopaohua]

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

[Elsa-zhang]

# 518. 零钱兑换 II
'''
'''
class Solution:
    def change(self, amount: int, coins: list[int]):
        n = len(coins)
        dp = [[0]*(amount+1) for _ in range(n+1)]
        # for i in range(n+1):
        #     dp[i][0] = 0
        dp[0][0]=1
        for i in range(amount+1):
            for j in range(1, n+1):
                coin = coins[j-1]
                dp[j][i] = dp[j-1][i]
                if i-coin >= 0:
                    dp[j][i] += dp[j][i-coin]
        return dp[-1][-1]

coins = [1,2,5]
amount = 5
solution = Solution()
ans = solution.change(amount, coins)
print(ans)

[whoam-challenge]

class Solution: def change(self, amount: int, coins: List[int]) -> int:

    dp = [0]*(amount+1)               
    dp[0] = 1   
    for coin in coins:                 
        for j in range(coin, amount+1): 
            dp[j] += dp[j-coin]

    return dp[amount]

[Jetery]

int f[5010];
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for(int & coin: coins){
            for(int i = 1; i <= amount; ++i)
                if(i - coin >= 0)
                    f[i] += f[i - coin]; 
        }
        return f[amount];
    }
};