Coin Change
Given a target of N cents and a collection of coins, how many ways can you form N cents? Tags: Dynamic Programming, Recursion
Try It!
Discussion
Video
Solution
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf') for i in range(amount + 1)]
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0 and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
if dp[amount] == float('inf'):
return -1
return dp[amount]