SimuVedaAlgorithms Lab Open in the lab

Dynamic programming / Intermediate

Coin Change Visualizer

dp[i] is the fewest coins for amount i. For each coin c, amount i can be reached from i − c with one more coin.

Start the Coin Change simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n·k)
Average timeO(n·k)
Worst timeO(n·k)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. dp[0] = 0, since 0 coins make amount 0. Everything else starts at ∞.
  2. Amount 1 with coin 1: dp[0] + 1 = 1, better than ∞.
  3. Amount 2 with coin 1: dp[1] + 1 = 2, better than ∞.
  4. Amount 2 with coin 2: dp[0] + 1 = 1, better than 2.
  5. Amount 3 with coin 1: dp[2] + 1 = 2, better than ∞.
  6. Amount 3 with coin 2: dp[1] + 1 = 2, not better than 2.
  7. Amount 4 with coin 1: dp[3] + 1 = 3, better than ∞.
  8. Amount 4 with coin 2: dp[2] + 1 = 2, better than 3.
  9. Amount 5 with coin 1: dp[4] + 1 = 3, better than ∞.
  10. Amount 5 with coin 2: dp[3] + 1 = 3, not better than 3.
  11. Amount 5 with coin 5: dp[0] + 1 = 1, better than 3.
  12. Amount 6 with coin 1: dp[5] + 1 = 2, better than ∞.
  13. Amount 6 with coin 2: dp[4] + 1 = 3, not better than 2.
  14. Amount 6 with coin 5: dp[1] + 1 = 2, not better than 2.
  15. Amount 7 with coin 1: dp[6] + 1 = 3, better than ∞.
  16. Amount 7 with coin 2: dp[5] + 1 = 2, better than 3.
  17. Amount 7 with coin 5: dp[2] + 1 = 2, not better than 2.
  18. Amount 8 with coin 1: dp[7] + 1 = 3, better than ∞.
  19. Amount 8 with coin 2: dp[6] + 1 = 3, not better than 3.
  20. Amount 8 with coin 5: dp[3] + 1 = 3, not better than 3.
  21. … 6 more steps …
  22. Amount 11 with coin 1: dp[10] + 1 = 3, better than ∞.
  23. Amount 11 with coin 2: dp[9] + 1 = 4, not better than 3.
  24. Amount 11 with coin 5: dp[6] + 1 = 3, not better than 3.
  25. The fewest coins for 11 is 3.

Try it with your own input →

1D DP: coin change in Java, Python, C++, C and JavaScript

int coinChange(int[] coins, int amount) {
  int[] dp = new int[amount + 1];
  Arrays.fill(dp, INF); dp[0] = 0;
  for (int i = 1; i <= amount; i++) {
    for (int c : coins) {
      if (c <= i && dp[i - c] + 1 < dp[i])
        dp[i] = dp[i - c] + 1;
    }
  }
  return dp[amount] == INF ? -1 : dp[amount];
}
def coin_change(coins, amount):
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i and dp[i - c] + 1 < dp[i]:
                dp[i] = dp[i - c] + 1
    return -1 if dp[amount] == INF else dp[amount]
int coinChange(const vector<int>& coins, int amount) {
  const int INF = INT_MAX - 1;
  vector<int> dp(amount + 1, INF); dp[0] = 0;
  for (int i = 1; i <= amount; i++) {
    for (int c : coins) {
      if (c <= i && dp[i - c] + 1 < dp[i])
        dp[i] = dp[i - c] + 1;
    }
  }
  return dp[amount] == INF ? -1 : dp[amount];
}
#include <limits.h>

int coinChange(int coins[], int nc, int amount) {
  int dp[amount + 1];
  for (int i = 1; i <= amount; i++) dp[i] = INT_MAX - 1;
  dp[0] = 0;
  for (int i = 1; i <= amount; i++) {
    for (int k = 0; k < nc; k++) {
      int c = coins[k];
      if (c <= i && dp[i - c] + 1 < dp[i])
        dp[i] = dp[i - c] + 1;
    }
  }
  return dp[amount] == INT_MAX - 1 ? -1 : dp[amount];
}
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i && dp[i - c] + 1 < dp[i])
        dp[i] = dp[i - c] + 1;
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

In an interview

LeetCode 322, Coin Change: the fewest coins that add up to the amount. Same idea: 279 Perfect Squares.

Greedy fails here. Try coins 1, 3, 4 with amount 6: greedy says 4 + 1 + 1, but 3 + 3 is better.

More dynamic programming