Coin Change

Dynamic ProgrammingUnbounded Knapsack

25 min

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example

Example 1:

Coins:

Amount:11

Fewest Coins:3

(e.g., 5 + 5 + 1)

Solution

This problem can be solved using bottom-up dynamic programming. We'll create a DP array, `dp`, of size `amount + 1`. `dp[i]` will store the minimum number of coins needed to make up the amount `i`.

We initialize the `dp` array with a value larger than any possible answer (e.g., `amount + 1`), and set `dp[0] = 0`. Then, we iterate through each amount from 1 to `amount`, and for each amount, we iterate through the available coins.

Algorithm Steps (DP)

Create a DP array `dp` of size `amount + 1` and fill it with `amount + 1`.
Set `dp[0] = 0`.
Iterate from `i = 1` to `amount`.
For each coin in `coins`:
If `i >= coin`, update `dp[i] = min(dp[i], 1 + dp[i - coin])`.
If `dp[amount]` is still `amount + 1`, it means the amount cannot be made up, so return -1. Otherwise, return `dp[amount]`.

Recurrence Relation

dp[i] = min(dp[i], 1 + dp[i - coin])

Coins:

DP Table

Step: 1 / 46

Coin Change Solution


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

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

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