518.Coin_Change_II(Medium).md

518. Coin Change II (Medium)

Date and Time: Aug 25, 2024, 23:26 (EST)

Link: https://leetcode.com/problems/coin-change-ii/

Question:

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

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

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

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

Output: 4

Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]

Output: 0

Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10]

Output: 1

Constraints:

• 1 <= coins.length <= 300

• 1 <= coins[i] <= 5000

• All the values of coins are unique.

• 0 <= amount <= 5000

Walk-through:

2D DP:

1. We can build a (amount + 1) * (coins + 1) dp table, which each dp[a][c] indicates the number of ways we can use c in coins to achieve a in amount. We first initialize dp[0] to be all 1, because the only way for all coins to achieve 0 is not using coins.

2. We then loop over (1, amount + 1), and visiting the coins backward to fill out the dp table from top to bottom, right to left.

3. Because the last column is the base case, so each time we intialize an entry in dp, we do dp[a][c] = dp[a][c-1] to first assign the new entry to be the value of its previous coin, because this new coin should have at least the number of ways of the previous coin to achieve a, then we check if a - coins[c] >= 0, so we know this new coin c can help to achieve a, then we add the row dp[a - coins[c]]'s number of ways to dp[a][c].

4. The final value is the last row, first element of the dp table.

      1  2  5
0   [[1, 1, 1, 1], 
1   [1, 0, 0, 0], 
2   [2, 1, 0, 0], 
3   [2, 0, 0, 0], 
4   [3, 1, 0, 0], 
5   [4, 1, 1, 0]]


dp[a][i] = dp[a][i-1] + dp[a-1][i]

  5 4 3 2 1 0
1 4 3 2 2 1 1 
2 1 1 0 1 0 1
5 1 0 0 0 0 1

Optimized 1d DP:

1. The optimized version we only store the previous column as prev, which is initialized to be all 0 and the first row will be 1 for a = 0. In the for loop we initialize a new column dp to store this column for current coin c for each amount a.

2. We repeatedly update prev = dp from right to left. And return the last element of dp as the final result.

Python DP Solution:

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

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

Time Complexity: $O(m * n)$, m is amount, n is length of coins.
Space Complexity: $O(m * n)$

Python Optimized DP Solution:

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

        for c in range(len(coins)-1, -1, -1):
            dp = [0] * (amount+1)
            dp[0] = 1   # a = 0 is always 1
            for a in range(1, amount+1):
                dp[a] = prev[a]     # Store previous col
                if a - coins[c] >= 0:
                    dp[a] += dp[a-coins[c]]
            prev = dp
        return dp[amount]

Time Complexity: $O(m * n)$, m is amount, n is length of coins.
Space Complexity: $O(m)$, since we only store one column.