Coin Change 2

Problem Statement

Given an array of integers coins representing denominations of values and a target amount amount, return the number of ways you can create amount with the values in coins

Solution

As the name suggests, this is a pretty similar problem to Coin Change. The logic there, if you forgot or haven't seen it, was Unbounded Knapsack due to the key characteristics of the problem:

1. DP
2. Items as coins
3. Constraint as the amount
4. Can use coins as many times as optimal

And guess what... these same principles apply. So whats different? Well now we are trying to calculate the number of ways to reach a given amount. Let dp[i] represent the number of ways we can reach j with our given coins. Given a coin value of c, what do we know to be true of our current value? In other words, lets say we have 2 coins: 3 and 4. If we want to calculate how many ways to get to 12, it is simply the number of ways to get to 9 and 8. Generally, dp[i] += dp[i-c]:

def change(self, amount: int, coins: List[int]) -> int:
	dp = [0] * (amount + 1)
	# Exactly 1 way to get to amount == 0
	dp[0] = 1
	for c in coins:
		for i in range(c, amount+1):
			dp[i] += dp[i-c]

	return dp[amount]

• Runtime Complexity: O(len(coins) * amount)
• Space Complexity: O(amount)