# 518. Coin Change 2
CYou are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
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
# Solution
Approach 1: DP with a 2D table. Let ways[i][v]
be the number of ways to sum to v using the first i types of coin.
Approach 2: DP with a 1D table. Let ways[i]
be the number of of ways summing to i dollars.
# Code (Python)
Approach 1:
def change(self, amount: int, coins: List[int]) -> int:
if not amount:
return 1
if not coins or amount < min(coins):
return 0
# ways[i][v]: number of ways to sum to v using the first i types of coin
ways = [[0 for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
for i in range(len(ways)):
ways[i][0] = 1
for i in range(1, len(ways)):
for v in range(len(ways[0])):
# total ways = ways without using the latest type of coin + ways substituting the last values with the new type of coin
ways[i][v] = ways[i-1][v]
if v >= coins[i-1]: # note for coins[i-1] (not coins[i]) because we're talking about the first i types of coin
ways[i][v] += ways[i][v-coins[i-1]]
return ways[-1][-1]
Approach 2:
def change(self, amount: int, coins: List[int]) -> int:
# Knapsack problem. ways[i]: num of ways for i dollars.
# For each type of coin, total ways = num ways where the last coin dollars uses the coin + num ways where it doesn't use that coin.
if not amount:
return 1
if not coins or amount < min(coins):
return 0
ways = [0 for _ in range(amount + 1)]
ways[0] = 1
# first use just 1 type of coin, then use coins 1 and 2, etc
for coin in coins:
for value in range(coin, len(ways)):
# add the number of ways where the last coin added was a coin with value='coin'
ways[value] += ways[value-coin]
return ways[-1]
# Code (C++)
Approach 1:
Approach 2: