【Day 64 】2021-11-12 - 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 位符号整数

[falsity]

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

[taojin1992]

Logic:

# Understand:
1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000

coins representing coins of different denominations

Return the number of combinations that make up that amount.

You may assume that you have an infinite number of each kind of coin.

Input: amount = 5, coins = [1,2,5]
Output: 4

5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

[1], 0

- Questions:
Is coins sorted? 

Edge cases:
1. if amount == 0, return 0

sort coins
2. if min_coin > amount, return 0

# Match & Plan:
at each coin index, choose it or not

We can start from the start of coin and go forward or start from the end and go backward. 

Assume start from coins array index = 0.

- How to represent a state? 

targetNum: target amount to achieve at this moment
curIndex: which coin are we looking at 

--static
coins

Adopt a cache: state -> number of ways, state is <curIndex, targetNum>

# Reivew: 
5
[5]
-> 1

Input: amount = 5, coins = [1,2,5]
Output: 4

5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

# Evaluate:
Before using the cache,
Time: O(2 ^ height) = O(2 ^ (amount/coin_min)) 
Space: stack, O(amount/coin_min)

Using the cache, 
Because state/key is <curIndex, targetSum>，curIndex ranges from 0 to coins.length - 1，targetSum ranges from 1 to amount, 

Space: stackdepth + cache = O(amount/coin_min) + O(coins.length * amount); 
Time: We touch each state once, O(coins.length * amount)

https://drive.google.com/file/d/16r4IF0CqkfIhMKBNuQdg-fGAbTjs172T/view?usp=sharing

-----------------------------------
How do we do it iteratively without recursion? 

similar to climbing stair problem: count[curAmount] is based on count[curAmount - coin]

count[0], to achieve 0 amount, use all the coins (0 coin used) -> count[0] = 1

count[amount]: denotes the number of combinations that make up amount, using all the coins

coins[0], coins[1], coins[2], ..., coins[coins.length - 1]

                          A                        B
count[amount] = count[amount - coins[0]] + count[amount - coins[1]] +... 

A. use one more coins[0] to achieve amount
B. use one more coins[1] to achieve amount
...

count[amount - coins[0]], the number of combinations that make up amount - coins[0]
e.g., assume we have 2 ways to achieve amount = 2, we have a coin val = 1, we have 2 ways to achieve 2 + 1 = 3. 

count[amount - coins[0]] = count[amount - coins[0] - coins[0]] + count[amount - coins[0] - coins[1]] +... 

count[amount - coins[0] - coins[0]]: use one more coins[0] to achieve amount - coins[0] from (amount - coins[0] - coins[0])

Time: O(amount * coins.length)
Space: O(amount)

Review:
amount = 3, coins = [1,2]

output: 2, {1,1,1}, {1,2}

count[val] += count[val - coins[i]];

- i = 0:
val = 1
count[1] += count[0]
count[1] = 1   {1}

val = 2     
count[2] += count[1] {1,1}
count[2] = 1

val = 3
count[3] += count[3-1]  {2,1}
count[3] = 1

- i = 1
val = 2
count[2] += count[2-2] {2}
count[2] = 2

val = 3
count[3] += count[3-2]  {1,2}
count[3] = 2

Code:

// Implement:
class Solution {
    // iterative
     public int change(int amount, int[] coins) {
         int[] count = new int[amount + 1];
         count[0] = 1;
         // bottom up, note the order for for loop to enable duplicate coins
         // i denotes: draw coins[i] in the last step, to achive val (can draw infinite times)
         for (int i = 0; i < coins.length; i++) {
            for (int val = coins[i]; val <= amount; val++) {
                /*
                System.out.println("i=" + i);
                System.out.println("val=" + val);
                */
                count[val] += count[val - coins[i]];
                //System.out.println(count[val]);
             }
         }

         return count[amount];
     }

    // backtracking + cache
    public int change1(int amount, int[] coins) {
        if (amount == 0) return 1; // ask the interviewer, return 0 or 1
        Arrays.sort(coins);
        if (coins[0] > amount) return 0;

        Map<Map.Entry<Integer, Integer>, Integer> cache = new HashMap<>();
        int curIndex = 0;
        return getChangeNum(coins, amount, curIndex, cache);
    }

    private int getChangeNum(int[] coins, int targetNum, int curIndex, Map<Map.Entry<Integer, Integer>, Integer> cache) {

        Map.Entry<Integer, Integer> state = Map.entry(curIndex, targetNum);
        // if pre-calculated
        if (cache.containsKey(state)) {
            return cache.get(state);
        }
        // base, be cautions with targetNum == 0 case

        // think about [5], 5
        if (targetNum == 0) { //fine if we don't use all the coins
            return 1;
        }
        else if (targetNum < 0) {
            return 0;
        }
        else if (curIndex == coins.length) { // explicitly targetNum > 0
            return 0;
        }

        // 2 branches: 
        // [5], 5        
        int chooseCur = getChangeNum(coins, targetNum - coins[curIndex], curIndex, cache);// chooseCurNotStay and chooseCurStay included in chooseCur case

        int notChooseCur = getChangeNum(coins, targetNum, curIndex + 1, cache);

        int total = chooseCur + notChooseCur;
        // insert to cache
        cache.put(state, total);
        return total;
    }
}

[xj-yan]

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 Complexity: O(n), Space Complexity: O(n)

[flagyk5]

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(1,amount+1):
                if j >= coins[i]: dp[j] += dp[j-coins[i]]
        return dp[-1]

[machuangmr]

代码

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

复杂度

• 时间复杂度 O(amount n)
• 空间复杂度O（amount）

[wangyifan2018]

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

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

        return dp[-1]

[ZETAVI]

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

复杂度分析

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

[zjsuper]

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

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

    return dp[-1]

[for123s]

代码

• 语言支持：C++

C++ Code:

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

[Lydia61]

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

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

        return dp[-1]

[Gjts]

语言 CSharp

• 时间复杂度：o(m∗n)
• 空间复杂度：o(m)

思路：动规背包，定义状态

code

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 = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

[kennyxcao]

518. Coin Change 2

Intuition

• DP

Code

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

Complexity Analysis

• Time: O(m * n),
• Space: O(m)
• m = amount
• n = len(coins)

[huzizailushang]

class Solution { public: int change(int amount, vector& coins) { vector dp(amount + 1, 0); //dp[j]：凑成总金额j的货币组合数为dp[j] 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]; } }; 时间复杂度：o(m∗n) 空间复杂度：o(m)

[Bingbinxu]

思路 这个题属于背包问题的类似问题, 每种面值的硬币都有选或不选两种选择。 顺着题目的要求定义dp数组:dp[i] = Σ dp[i - coin[i]] (coin[i] ∈ coins) 代码(C++)

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] + dp[i];
            }
        }
        return dp[amount];
    }
};

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

[BpointA]

思路

学会了组合的背包，长见识了

Python代码

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

[sumukeio]

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

[Richard-LYF]

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

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

    return dp[amount]