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]