Preset

Target Amount

SPEED

1D DP ARRAY: dp[amount]

Active

Compare dp[a−coin]

Updated

Selected

RECONSTRUCTED COIN SELECTION0 coins

Step through or jump to reconstruction to see coin picks

coinChange.js

1function coinChange(coins, amount) {

2 const dp = Array(amount + 1).fill(Infinity);

3 dp[0] = 0;

4 const lastCoin = Array(amount + 1).fill(0);

6 for (const coin of coins) {

7 for (let a = coin; a <= amount; a++) {

8 const candidate = dp[a - coin] + 1;

9 if (candidate < dp[a]) {

10 dp[a] = candidate;

11 lastCoin[a] = coin;

12 }

13 }

14 }

16 // Reconstruct coin selection

17 const selected = [];

18 let rem = amount;

19 while (rem > 0) {

20 selected.push(lastCoin[rem]);

21 rem -= lastCoin[rem];

22 }

23 return { minCoins: dp[amount], selected };

24}

About the Coin Change algorithm

Find the minimum number of coins that make up an amount. Classic unbounded knapsack variant.

Category: Dynamic Programming
Difficulty: Medium
Time complexity: O(n·amount)
Space complexity: O(amount)