Coin Change

Dynamic Programming
Medium

Approach

Diagrams

Analysis

Time

O(mn)

Space

O(n)
class Solution:
    def coinChange(self, coins, totalAmount):
        MAX = float('inf')
        dp = [MAX] * (totalAmount + 1)
        dp[0] = 0

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

        return dp[-1] if dp[-1] < MAX else -1

Learn

#Dynamic Programming

Videos