#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/dynamic-programming-1d/coin-change-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/dynamic-programming-1d/coin-change-implementation

Repovive

LeetCode 322 Coin Change - Implementation - Dynamic Programming - 1D | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 322 Coin Change - Implementation

The approach

Bottom-up DP. Try each coin for each amount.

def coinChange(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0

for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i and dp[i - coin] != float('inf'):
            dp[i] = min(dp[i], dp[i - coin] + 1)

return dp[amount] if dp[amount] != float('inf') else -1

$O(\text{amount} \times n)$ time, $O(\text{amount})$ space.