Leetcode 518. Coin Change 2 (python+cpp)

题目

解析

如果做过332 coin change1的话，这道题目相对来说应该会更简单。因为思路非常清晰，对于某个状态来说，只有两种可能性，取当前的coin或者不取当前的coin，分别对应了两个sub problem。所以定义一个二维dp数组,状态转移方程如下：

# dp[i][j] 代表用前i个coin，有多少种方式组成j
dp[i][j] = dp[i-1][j] # 代表不取当前coin
+ dp[i][j-coin] # 代表取当前coin

这边有一点要注意的是初始化，当amount=0的时候，我们认为只有一种方式能够达成，就是不做任何操作
python代码如下：

class Solution:def change(self, amount: int, coins: List[int]) -> int:m = len(coins)n = amountdp = [[0]*(n+1) for _ in range(m+1)]for i in range(m+1):dp[i][0] = 1for i in range(1,m+1):for j in range(n+1):if j>=coins[i-1]:dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]else:dp[i][j] = dp[i-1][j]return dp[-1][-1]

这道题目也可以用coin change 1里面直接遍历coin的方式来做，这样可以用一维dp解决，不过我更建议记二维dp，因为更直观，面试的时候也更容易想到
python代码如下：

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

C++版本如下：

class Solution {
    
public:int change(int amount, vector<int>& coins) {
    vector<int> 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];}
};