【Day 64 】2022-02-13 - 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 位符号整数

[Richard-LYF]

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

    dp = [0] *(amount+1)

    dp[0] = 1

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

    return dp[-1]

[yetfan]

思路 硬币的遍历要有序，从小到大，保证不会重复

每个dp要推的东西就是： 【最后一个硬币用 coin 的时候达到amount的组合数】 即 【不用这个 coin 之前 达到amount-coin的组合数 dp[amount-coin]】

统计的时候再加上 之前不用该coin达到amount的组合数 dp[amount] new = dp[amount] old + 【dp[amount-coin]】 初始状态dp[0] = 1（一个都不选，结果组合为0）

代码

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

        return dp[amount]

复杂度 时间 O(amount * n) 空间 O(amount)

---

举个例子 coins=[1,2,3], amount=10 外层循环依次开始算123 第一圈，遍历coin 全1能凑出的结果, 说白了也就都是一种可能 dp[1] = 1, dp[2] = 1 .... dp[10] = 1 第二圈，开始加入coin = 2的考虑了，要从dp[2]开始算 dp[2] = old dp[2] + dp[2-2] dp[3] = old dp[3] + dp[3-2] ... dp[6] = old dp[6] + dp[6-2]
(这个dp[6-2]中包含 使用coin1的和使用coin2达到的dp[4]的和， 【1,1,1,1】【1,1,2】【2,2】 保证3会在下一个外部循环内，不会出现在2前面而导致重复【1,3】+【2】) 第三圈，才开始3... 上述情况dp[6] 会在这里计入【1,2】+【3】的情况

[ZJP1483469269]

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

[charlestang]

思路

动态规划

代码

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

        for c in coins:
            for i in range(c, amount + 1):
                dp[i] += dp[i - c]
        return dp[amount]

[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]

[Brent-Liu]

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

dp = [0] *(amount+1)

dp[0] = 1

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

return dp[-1]

[CoreJa]

思路

• 滚动DP：常规背包问题，求和为amount的不同硬币的组合数，用滚动DP完成即可。这里硬币数是无限的，所以直接从前往后遍历即可。具体的，把amount作为一个维度， 设dp[i][j]为从0到i的硬币中任取若干个，使其和为j的最大数量。考虑取用coins[i]硬币和不取用的情况，不取用则$dp[i][j]=dp[i-1][j]$，取用则有$dp[i][j]=dp[i-1][j-coins[i]]+1$，要求最大数量，所以把二者相加即可。而次态仅与当前态相关，所以应用滚动数组的方式，状态方程为$dp[j]=dp[j-coins[i]]+1+dp[j]$，复杂度$O(n*amount)$

代码

class Solution:
    # 滚动DP：常规背包问题，求和为`amount`的不同硬币的组合数，用滚动DP完成即可。这里硬币数是无限的，所以直接从前往后遍历即可。
    # 具体的，把amount作为一个维度， 设`dp[i][j]`为从0到`i`的硬币中任取若干个，使其和为`j`的最大数量。考虑取用`coins[i]`
    # 硬币和不取用的情况，不取用则$dp[i][j]=dp[i-1][j]$，取用则有$dp[i][j]=dp[i-1][j-coins[i]]+1$，要求最大数量，所以
    # 把二者相加即可。而次态仅与当前态相关，所以应用滚动数组的方式，状态方程为$dp[j]=dp[j-coins[i]]+1+dp[j]$
    def change(self, amount: int, coins: List[int]) -> int:
        coins.sort(reverse=True)
        dp = [1] + [0] * amount
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]
        return dp[-1]

[XinnXuu]

Solution

背包问题，只要 coin<剩下的容量就放进去，并更新 dp 数组。

Code

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        //dp[i] : #make up to amount i
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++){
            for (int j = 1; j < amount + 1; j++){
                if (coins[i] <= j){
                    dp[j] += dp[j - coins[i]];
                } 
            }
        }
        return dp[amount];
    }
}

Complexity

• Time Complexity: O(amount*n)
• Space Complexity: O(amount)

[zhangzz2015]

思路

• 采用DP方法，dp[i][j] 选择从 0 到 i的 Coin 当amount为 j 的组合数，dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]] 当j=0 时候，只有1种方法。方法1，采用两维dp，时间复杂度为O(nm)，空间复杂度为O(nm)，方法2，压缩到1维，空间复杂度为 O(m)，n为硬币种类，m为总数。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int change(int amount, vector<int>& coins) {

        // Time O(n*m) Space O(n*m)  Cost: 15min.   
        ///   dp[i][j]    chose from 0 to i coins and get target amount j. combination
        //    dp[i][j]    dp[i][j] =  dp[i-1][j]  +  loop k from 0 to max num coins[i]. dp[i-1][j-coins[i]*k]
        //    dp[i][j]    dp[i][j] = dp[i-1][j] +  dp[i][j - coins[i]] ; 
        //   we can improve it further to optimize memory to O(n)

        vector<int> dp(amount+1, 0); 
        dp[0] =1; 
        for(int i=0; i<coins.size(); i++)
        {

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

    int method1(int amount, vector<int>& coins)
    {
        vector<vector<int>> dp(coins.size()+1, vector<int>(amount+1, 0)); 

        for(int i=0; i<=coins.size(); i++)
        {
            for(int j=0; j<=amount; j++)
            {
                if(j==0)
                    dp[i][j] = 1; 
                else if(i==0)
                    dp[i][j] = 0; 
                else
                {
                    int k=0; 
                   /* while(j >=coins[i-1]*k)
                    {
                        dp[i][j] +=dp[i-1][j-coins[i-1]*k]; 
                        k++;
                    }     */ 
                    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[coins.size()][amount];         
    }
};

[zwx0641]

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

[falconruo]

思路:

DP, 使用二维数组dp[i][j]表示使用前i种硬币[1, i]来组成钱数j的最大组合数 dp[i][j] = dp[i - 1][j], 不选择第i个硬币 dp[i][j - coins[i - 1]], 不选择第i个硬币

可以优化成一维数组 dp[i] = dp[i] + dp[i - coins[j]]

复杂度分析:

• 时间复杂度: O(N * amount)，N为数组coins长度, amount为金额总数,
• 空间复杂度: O(amount)

代码(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 j = coin; j <= amount; j++) {
                if (j >= coin) // choose coin
                    dp[j] += dp[j - coin];
            }
        }

        return dp[amount];
    }
};

[ZacheryCao]

Idea

DP

Code

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

Complexity:

Time:O(N *amount) Space: O(amount)

[mannnn6]

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        //dp[i] : #make up to amount i
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++){
            for (int j = 1; j < amount + 1; j++){
                if (coins[i] <= j){
                    dp[j] += dp[j - coins[i]];
                } 
            }
        }
        return dp[amount];
    }
}

[rzhao010]

    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];
    }

[Tesla-1i]

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

        return dp[amount]

[QinhaoChang]

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

[yan0327]

func change(amount int, coins []int) int {
    dp := make([]int,amount+1)
    dp[0] = 1
    for _,coin := range coins{
        for i:=coin;i<=amount;i++{
            dp[i] += dp[i-coin]
        }
    }
    return dp[amount]
}

[declan92]

思路

1. dp[i][j]表示在第i枚硬币时总金额为j的硬币组合数;
2. dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j]; 步骤
3. 定义dp数组,int[amount+1],初始化dp[0] = 1
4. 双循环嵌套(内循环正序),dp[j] += dp[j-coins[i]]
5. 返回dp[len(coins)-1][amount]; java code

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

   时间:$O(n*m)$
   空间:$O(m)$

[tangjy149]

代码

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

[ginnydyy]

Problem

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

Notes

• DP
• dp[i] means the number of combination of coins to form total i. So the problem is converted to find the dp[amount]
• The dp formula is dp[i] = sum(dp[i - coin[j]) where coin[j] <= i. Because based on dp[i - coin[j]], we only need to add one coin[j] to it, then we get the total i. So all the dp[i - coin[j]] form the dp[i], as long as coin[j] <= i.
• Details: the problem is asking the number of combination, so need to consider removing the duplicate combinations. Thus, the way to embed the for loops matter.

Solution

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        // this way to embed the loop causes duplicate combination
        // i.e. amount = 3, coins[1, 2]
        // combination (1, 2) and (2, 1) will becount seperately, but they are duplicate
        // for(int i = 1; i <= amount; i++){
        //     for(int coin: coins){
        //         if(coin <= i){
        //             dp[i] += dp[i - coin];
        //         }
        //     }
        // }

        // this way to embed the loop guarantees each type of coin will be iterated only once
        // for each amount, each coin will be considered only once in order 
        for(int coin: coins){
            for(int i = coin; i <= amount; i++){
                dp[i] += dp[i - coin];
            }
        }        

        return dp[amount];
    }
}

Complexity

• Time: O(n amount), n is the length of the given coins array. We iterate all the coin types, and for each coin type, iterate all the total value of the coins. In each iteration, it costs O(1), so overall is O(n amount).
• Space: O(amount), extra space is required for the dp array.

[xuhzyy]

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: 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[-1]

[cszys888]

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

time complexity: O(amount*N), where N stands for length of coins space complexity: O(amount)

[haixiaolu]

思路

DP

代码 / Python

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

        # dp
        dp = [0] * (amount + 1)
        dp[0] = 1

        for i in range(len(coins) - 1, -1, -1):
            nextDp = [0] * (amount + 1)
            nextDp[0] = 1

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

        return dp[amount]

复杂度分析：

• 时间复杂度： O( n * m)
• 空间复杂度： O(n)

[tongxw]

思路

完全背包

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

        return dp[amount];
    }
}

TC: O(n * amount) SC: O(amount)

[stackvoid]

思路

背包问题

代码

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];
    }
}

算法复杂度分析

TIme O(N) Space O(N)

[LannyX]

思路

背包

代码

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

复杂度分析

• 时间复杂度：O(nm)
• 空间复杂度：O(m)

[googidaddy]

const change = (amount, coins) => { let dp = Array(amount + 1).fill(0); dp[0] = 1;

for(let i =0; i < coins.length; i++) {
    for(let j = coins[i]; j <= amount; j++) {
        dp[j] += dp[j - coins[i]];
    }
}

return dp[amount];

}

[baddate]

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];
    }
};

[1149004121]

518. 零钱兑换 II

思路

背包问题。

代码

var change = function(amount, coins) {
    let dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    const n = coins.length;
    for(let i = 0; i < n; i++){
        for(let j = 1; j <= amount; j++){
            if(j - coins[i] >= 0){
                dp[j] = dp[j] + dp[j - coins[i]];
            };
        }
    };
    return dp[amount];
};

复杂度分析

• 时间复杂度：O(amount*n)。
• 空间复杂度：O(amount)。

[Toms-BigData]

func change(amount int, coins []int) int { dp := make([]int, amount+1) dp[0] = 1 for _, coin := range coins { for i := coin; i <= amount; i++ { dp[i] += dp[i-coin] } } return dp[amount] }

[zhiyuanpeng]

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

[GaoMinghao]

思路

先用未经优化的DP打个卡

代码

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

[iambigchen]

代码

var change = function(amount, coins) {
    let dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    const n = coins.length;
    for(let i = 0; i < n; i++){
        for(let j = 1; j <= amount; j++){
            if(j - coins[i] >= 0){
                dp[j] = dp[j] + dp[j - coins[i]];
            };
        }
    };
    return dp[amount];
};

[Myleswork]

思路

和Day63的题一个道理

其实优化后的DFS也能做，回溯法

代码

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        dp[0] = 1; //啥都不挑，就这一种方案
        for(int i = 0;i<coins.size();i++){
            for(int j = coins[i];j<amount+1;j++){
                if(j>=coins[i]) dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

复杂度分析

时间复杂度：O(amount)

空间复杂度：O(amount)

[Today-fine]

学习网友的代码

class Solution {

    public int change(int amount, int[] coins) {

        int num = coins.length;
        int[][] dp = new int[num+1][amount+1];

        for(int i = 0; i <= num; i++)
            dp[i][0] = 1;

        for(int i = 1; i <= num; i++) {

            for(int j = 1; j <= amount; j++) {

                for(int k = 0; k * coins[i-1] <= j; k++) {

                    dp[i][j] = dp[i][j] + dp[i-1][j-k*coins[i-1]];

                }
            }
        }

        return dp[num][amount];
    }
}

[wdwxw]

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]; } }

[bluetomlee]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int dp[amount+1];
        memset(dp, 0, sizeof(dp)); //初始化数组为0
        dp[0] = 1;
        for (int coin : coins){ //枚举硬币
            for (int j = 1; j <= amount; j++){ //枚举金额
                if (j < coin) continue; // coin不能大于amount
                dp[j] += dp[j-coin];
            }
        }
        return dp[amount];
    }
};

[callmeerika]

思路

动态规划

代码

var change = function(amount, coins) {
    let dp = new Array(amount+1).fill(0);
    dp[0] = 1;
    for(let i = 0;i < coins.length;i++) {
        let num = coins[i];
        for(let j = num; j <= amount; j++) {
            dp[j] += dp[j - num];
        }
    }
    return dp[amount];
};

复杂度

时间复杂度：O(n*amount)
空间复杂度：O(amount)

[wbcz]

var change = function (amount, coins) { const dp = Array.from({ length: amount + 1 }).fill(0); dp[0] = 1; for (let coin of coins) { for (let i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; };

[kbfx1234]

518. 零钱兑换 II

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

[spacker-343]

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

[tian-pengfei]

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 = 1; i <= amount; ++i) {
                if(i-coin>=0)dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }
};

[Neal0408]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [1] + [0]*amount # 初始状态
        for i in coins:
            for j in range(i,amount+1):
                dp[j] += dp[j-i] # 状态转移
        return dp[-1]

[MissNanLan]

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
  const dp = Array.from({ length: amount + 1 }).fill(0);
  dp[0] = 1;
  for (let coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }
  console.log("dp", dp);
  return dp[amount];
};

// 这个题关键在于能写出状态转移方程吧

复杂度分析

令 n 是 coins 的数量, m 是 amount

时间复杂度: O(m*n)

空间复杂度: O(m)

[alongchong]

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];
    }
}

[moirobinzhang]

Code:

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

    return dp[amount];
}

}

[Hacker90]

int change(int amount, int[] coins) { int n = coins.length; int[] dp = new int[amount + 1]; dp[0] = 1; // base case 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];

}

[shamworld]

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

[hdyhdy]

func change(amount int, coins []int) int {
    dp := make([]int,amount+1)
    dp[0] = 1 
    for _,coin := range coins{
        for i := coin; i < amount + 1 ; i ++ {
            dp[i] += dp[i - coin]
        }
    }
    return dp[amount]
}

[kite-fly6618]

思路

动态规划

代码

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

复杂度

时间复杂度:O(MN) M-> coin数组的长度，n->amount
空间复杂度:O(N)