Visualizers

Coin Change Visualizer

Animate finding the minimum coins for a target amount using a 1D DP array.

native Client-side

Target Amount (1-15)

Coins (comma-separated)

Speed

Ready to compute.

Execution Log

Min Coins Needed: -

Coins Chosen: -

Current Action:

Idle

Legend:

Uncomputed

Active Lookups

Calculated Value

Backtrack Path

Coin Change DP Algorithm

The Coin Change problem is a classic dynamic programming problem. Given coins of different denominations and a total target amount, find the minimum number of coins that make up that amount. If that amount of money cannot be made up, return -1.

Dynamic Programming Relation

We maintain a 1D DP table `dp[i]` representing the minimum coins needed for amount $i$:

Base Case: `dp[0] = 0` (0 coins to make amount 0)
Relation: `dp[i] = min(dp[i], dp[i - coin] + 1)` for each coin where `coin <= i`

Implementation

function coinChange(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

def coin_change(coins, amount):
    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], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

import java.util.Arrays;

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

#include <vector>
#include <algorithm>

int coinChange(const std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; ++i) {
        for (int coin : coins) {
            if (i - coin >= 0) {
                dp[i] = std::min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Related Tools

Big-O Visualizer

Interactive growth-curve chart for common complexity classes.

Data Structure Visualizer

Animated operations on linked lists, trees, stacks and hash tables.

Algorithm Visualizer

Step-through animations for sorting and pathfinding algorithms.