Dynamic Programming • Unbounded Knapsack

Coin Change

Find the minimum number of coins needed to make up a given amount. You can use each coin infinitely many times.

Overview

This is a classic unbounded knapsack problem. We want to fill a knapsack of capacity `amount` using minimum items of given weights `coins`.

Let `dp[i]` be the minimum number of coins needed to make amount `i`. Initially, `dp[0] = 0` and all other `dp[i] = infinity`.

For each coin, we can try to add it to any reachable state `i - coin`. The new state is `dp[i] = Math.min(dp[i], dp[i - coin] + 1)`.

By iterating through each coin sequentially and updating the DP table left-to-right, we implicitly allow the same coin to be used multiple times.

Coins:Amount:

dp[0]0

dp[1]inf

dp[2]inf

dp[3]inf

dp[4]inf

dp[5]inf

dp[6]inf

dp[7]inf

dp[8]inf

dp[9]inf

dp[10]inf

dp[11]inf

Code Tracker

:::

1let dp = Array(amount + 1).fill(Infinity); dp[0] = 0;

2for (let coin of coins) {

3 for (let i = coin; i <= amount; i++) {

4 dp[i] = Math.min(dp[i], dp[i - coin] + 1);

5 }

6}