Dynamic Programming

Coin Change

Fewest coins for an amount — where greedy fails and DP works.

TimeO(n·amount)SpaceO(amount)CategoryDynamic Programming

Visualize this — step by stepNo signup needed.

Coin Change asks for the minimum number of coins summing to a target. `dp[i]` is the answer for amount i, built from smaller amounts: for each coin c, `dp[i]` can be `dp[i-c] + 1`, and we keep the smallest.

It is the standard counter-example to greedy reasoning. With coins {1, 3, 4} and target 6, taking the largest first gives 4+1+1 = three coins, while the optimum is 3+3 = two. The DP considers every coin at every amount and cannot be fooled.

It is also one-dimensional, which makes it a gentle first DP. AlgoLens shows `dp` filling left to right, so you can see the moment the greedy answer gets beaten.

The code

coin_change.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> coins = {1, 3, 4};
    int target = 6;

    vector<int> dp(target + 1, 1e9);
    dp[0] = 0;

    for (int i = 1; i <= target; i++) {
        for (int c : coins) {
            if (c <= i) dp[i] = min(dp[i], dp[i - c] + 1);
        }
    }

    cout << dp[target] << '\n';
    return 0;
}

Open this in the visualizer

Now run your own Coin Change

AlgoLens traces your code — arrays, graphs, trees and recursion — from a real execution, so you see how it actually behaves, not a canned animation.

Paste your code

Keep going

Fibonacci with Memoization

Turn exponential recursion into linear time by caching subresults.

0/1 Knapsack

Take it or leave it — the DP table that defines the field.

Longest Common Subsequence

How much two strings share, in order — the basis of diff.

Bubble Sort

The simplest sort — watch the largest value bubble to the end each pass.