Coin Change Problem (Dynamic Programming)

Coin Change is one of the most well-known dynamic programming problems. Given a target amount and a set of coin denominations, we need to determine:

the minimum number of coins needed to make the amount, or
the number of different ways to make the amount using the coins.

In this lesson, we will focus on the problem of the minimum number of coins.

Problem Definition

We are given an array of coins coins[] and a target amount S. Each coin can be used an unlimited number of times. We need to find the minimum number of coins needed to make the amount S.

Example:

Coins: {1, 3, 4}
Amount: 6

Answer: 2 coins (3 + 3; 4 + 1 + 1 requires 3 coins).

Why Dynamic Programming?

The problem has:

overlapping subproblems – the same amount is computed multiple times
optimal substructure – the optimal solution for amount S depends on optimal solutions for smaller amounts

This makes it an ideal candidate for dynamic programming.

DP Idea and State

We define an array:


dp[x] = the minimum number of coins needed to make amount x

Base case:

dp[0] = 0 (no coins are needed to make amount 0)
all other values are initially set to “infinity”

Transition:


dp[x] = min(dp[x], dp[x - coin] + 1)

for each coin coin and each amount x ≥ coin.

Bottom-Up Implementation (C++)


#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {

    // n - number of coins
    // S - target amount
    int n, S;
    cin >> n >> S;

    // Read the coin values
    vector<int> coins(n);
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }

    // dp[x] = the minimum number of coins needed to make amount x
    // Initialize all values to INT_MAX (representing "infinity")
    vector<int> dp(S + 1, INT_MAX);

    // Base case: no coins are needed to make amount 0
    dp[0] = 0;

    // Calculate dp values for all amounts from 1 to S
    for (int x = 1; x <= S; x++) {

        // Try every coin
        for (int coin : coins) {

            // Check whether the coin can be used
            // and the previous state is not "infinity"
            if (x - coin >= 0 && dp[x - coin] != INT_MAX) {

                // Choose the smaller value:
                // - the current dp[x]
                // - or dp[x - coin] + 1 (using one additional coin)
                dp[x] = min(dp[x], dp[x - coin] + 1);
            }
        }
    }

    // If dp[S] is still INT_MAX, the target amount cannot be formed
    if (dp[S] == INT_MAX) {
        cout << "Cannot form the target amount";
    } else {
        cout << "Minimum number of coins: " << dp[S];
    }

    return 0;
}

Time and Space Complexity

Time complexity: O(n · S)
Space complexity: O(S)

where n is the number of coin denominations, and S is the target amount.

Coin Change Visualization (Minimum Number of Coins)

This visualization shows the DP array being filled step by step to find the minimum number of coins. Coins: {1, 3, 4}, Amount: 6.

Coin Change Variations

Coin Change has several common variations:

number of ways to make an amount
limited number of coins
whether different coin orders count as distinct ways

All these variants can be solved with dynamic programming by making small changes to the state and transition.

Pored osnovnog problema the minimum number of coins, Coin Change ima nekoliko čestih varijacija. Razumevanje ovih varijanti pomaže pri rešavanju složenijih zadataka iz dinamičkog programiranja.

1️⃣ Number of Ways to Make an Amount (Order Does Not Matter)

Goal: determine how many different coin combinations can make the amount S. Each coin can be used without limit, but the order of the coins does not matter.

DP state:dp[x] represents the number of ways to make amount x.


// Initialization
dp[0] = 1;  // postoji 1 način da se formira suma 0: ništa ne uzimamo
for (int coin : coins) {
    for (int x = coin; x <= S; x++) {
        dp[x] += dp[x - coin]; // add all ways to form x - coin
    }
}

Example: coins {1, 3, 4}, amount 6 → number of combinations = 4: - {1,1,1,1,1,1} - {1,1,4} - {3,3} - {1,1,1,3}

2️⃣ Number of Ways to Make an Amount (Order Matters)

If coin order matters, the order of the DP loops changes:


// Initialization
dp[0] = 1;
for (int x = 1; x <= S; x++) {
    for (int coin : coins) {
        if (x - coin >= 0) {
            dp[x] += dp[x - coin]; // add all ways from the previous amount
        }
    }
}

Example: coins {1, 3, 4}, amount 6 → different sequences are counted separately when order matters.

Coin Change Visualization — Number of Ways to Make an Amount

This visualization shows the DP array being filled step by step to count the different coin combinations. Coins: {1, 3, 4}, Amount: 6. Coin order does not matter.

Coin Change — Counting Ways (Visual Walkthrough)

Example:

Coins: {1, 2, 3}
Target amount: 4

Initializing the DP Array

We define dp[x] = number of ways to make an amount x.


dp[0] = 1   // there is 1 way to form the sum 0: we take nothing
dp[1..4] = 0

Home table:

x	0	1	2	3	4
dp[x]	1	0	0	0	0

Step 1: coin = 1

We add all combinations that end with 1:

x	0	1	2	3	4
dp[x]	1	1	1	1	1

Explanation:

dp[1] += dp[0] → 1
dp[2] += dp[1] → 1
dp[3] += dp[2] → 1
dp[4] += dp[3] → 1

Step 2: coin = 2

We add all combinations that end with 2:

x	0	1	2	3	4
dp[x]	1	1	2	2	3

Explanation:

dp[2] += dp[0] → 1 + 1 = 2 (combinations: 1+1, 2)
dp[3] += dp[1] → 1 + 1 = 2 (combinations: 1+1+1, 1+2)
dp[4] += dp[2] → 1 + 2 = 3 (combinations: 1+1+1+1, 1+1+2, 2+2)

Detaljno objašnjenje reda: dp[4] += dp[2]

At this point, we have:

dp[4] = 1 → combinations: 1+1+1+1
dp[2] = 2 → combinations: 1+1 i 2

Now we ask:

How many ways are there to make 4 if the last coin is 2?

If the last coin must be 2, then the amount we must make beforehand is:


4 - 2 = 2

The number of ways to make 2 je dp[2] = 2.

We can extend each of those combinations by adding one more coin 2:

(1 + 1) + 2 → 1 + 1 + 2
(2) + 2 → 2 + 2

Therefore, we get 2 new combinations.

Since we already had 1 kombinaciju (1+1+1+1), the total becomes:


1 (stara) + 2 (nove) = 3

That is why we do this:


dp[4] += dp[2]

Intuitively:

“Take every way to make 2 and add one more 2 to each.”

Vizuelni dijagram grananja combination

Let us see how the combinations for amount 4 are formed when processing coin 2.

We know that:

dp[2] = 2 → (1+1) i (2)

Now we add one more coin to each of those combinations 2:


                (pravimo 4 dodavanjem 2)

                       4
                       |
            ------------------------
            |                      |
        (1+1)                  (2)
            |                      |
        (1+1)+2                (2)+2
            |                      |
        1+1+2                  2+2

These are two new combinations that end with 2.

Together with the existing combination:


1 + 1 + 1 + 1

At this point, we have a total of 3 combinations for amount 4.

Ključna intuicija

We can think of it this way:

dp[x] = the total number of combinations for x
dp[x - coin] = the number of combinations we can extend by adding that coin

Each combination for x - coin becomes a new combination for x when we add one more coin.

That is why we add:


dp[x] += dp[x - coin]

This is a systematic way to build combinations layer by layer.

Step 3: coin = 3

We add all combinations that end with 3:

x	0	1	2	3	4
dp[x]	1	1	2	3	4

Explanation:

dp[3] += dp[0] → 2 + 1 = 3 (kombinacije: 1+1+1, 1+2, 3)
dp[4] += dp[1] → 3 + 1 = 4 (kombinacije: 1+1+1+1, 1+1+2, 2+2, 1+3)

Final Result

The number of different combinations for amount 4 je: dp[4] = 4

This approach guarantees that the order of the coins does not change the combination, because we process each coin from the outside and build combinations systematically.

3️⃣ Limited Number of Coins

If there is a limit on how many times each coin can be used, it is necessary to keep track of how many coins have been used. This is usually done with 2D DP:


// dp[i][x] = the minimum number of coins for amount x koristeći prvih i kovanica
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
    for (int x = 0; x <= S; x++) {
        dp[i][x] = dp[i-1][x]; // We don't use that coin.
        for (int k = 1; k <= limit[i] && k*coins[i-1] <= x; k++) {
            if (dp[i-1][x - k*coins[i-1]] != INT_MAX)
                dp[i][x] = min(dp[i][x], dp[i-1][x - k*coins[i-1]] + k);
        }
    }
}

This is similar to 0/1 Knapsack, but allows multiple copies of each coin denomination.

All these variants can be solved with dynamic programming by making small changes to the state and transition. Understanding these variations makes it easier to solve problems that combine:

minimum number of coins
number combination
restrictions on the use of coins

Visualization — Number of Ways (Order Matters)

Coins: {1,3,4} Amount: 6 Now different orders count as different ways.

Visualization — Limited Number of Coins

Coins: {1,3,4} Limit: {2,1,1} Amount: 6

Greedy Algorithms — A Counterexample

Greedy algorithms choose the current best solution at each step, without thinking about future consequences.

Sometimes it gives an optimal solution (eg activities with the earliest completion), but it often leads to the wrong result.

An Example Where Greedy Does NOT Work

Consider the Coin Change problem:

Coins: {1, 3, 4}
Amount: 6

A greedy strategy would be: "Always set the biggest coin possible."

Steps:

Take 4 → remaining 2
Take 1 → remaining 1
Take 1 → remaining 0

The greedy solution uses 3 coins (4 + 1 + 1).

But the optimal solution is:

3 + 3 = 6

which uses only 2 kovanice.

Conclusion

The Greedy algorithm made the locally best decisions, but did not find a global optimal solution.

Therefore:

If a problem has optimal substructure and overlapping subproblems, dynamic programming may be suitable.
If you can prove that a locally optimal choice always leads to the global optimum, the greedy approach is valid.

Before applying greedy, always try to find a counter example. If you find it - greedy is not a safe choice.

Greedy vs. Dynamic Programming (Visual Comparison)

Consider the same example:

Coins: {1, 3, 4}
Amount: 6

Greedy Approach

Strategy: “Always take the largest possible coin.”

Step	Coin Chosen	Remaining Amount
1	4	2
2	1	1
3	1	0

Greedy result: 3 kovanice

⚠ Problem: the algorithm never considered the combination 3 + 3.

Dynamic Programming (DP)

DP computes the optimal solution for every amount from 0 do 6.

Definition:


dp[x] = the minimum number of coins for amount x

Resulting table:

Suma x	0	1	2	3	4	5	6
dp[x]	0	1	2	1	1	2	2

DP result: 2 coins

Key Difference

Greedy	Dynamic programming
Makes a local decision	Considers all sub-solutions
Does not check alternatives	Keeps optimal results for smaller sums
Quick and easy	Surely gives the optimal solution
Could be wrong	Doesn't miss the optimal combination

Intuition

Greedy asks: “What is best right now?”

DP thinks: "What was best for all the minor problems, so I'll use that to get the best solution now.”

That is why DP can often be seen as a "safe version" of the greedy approach, which checks all possibilities.

Connections to Other DP Problems

The Coin Change problem is closely related to several other classic dynamic programming problems. Understanding these connections helps you to:

recognize DP patterns more easily
apply similar techniques to different problems
solve contest problems faster

1. 0/1 Knapsack Problem

This is one of the most famous DP problems. The goal is to maximize the total value of the items that fit in the backpack of W capacity, where each item can be taken at most once.

The Coin Change minimum-coin problem is essentially **a special case of “Unbounded Knapsack”** — gde:

item weights correspond to coin denominations
each “item” can be used an unlimited number of times
the goal is to minimize the number of items (coins) used

On the other hand, the 0/1 Knapsack has an important difference: each item can be taken at most once, resulting in a different DP formula and 2D DP table. You can see a detailed explanation and examples here:

DP: The 0/1 Knapsack Problem

2. Subset Sum Problem

Subset Sum is another simple but very important DP task: A set of numbers and a target amount T are given. Check if there is a subset whose sum is **true T**.

The DP approach uses the array dp[x] to indicate whether the sum x is possible. This is very close Coin Change variants where we only check the possibility of forming a sum, not the number of ways or minimum coins.

Read the full lesson here:

DP: The Subset Sum Problem

3. Knapsack Variants — Unbounded and Bounded

Technically, Coin Change is an **Unbounded Knapsack** problem: svaku kovanicu možemo koristiti više puta. To je zato što prelaz u DP koristi samo jednu dimenziju i dozvoljava višestruko korišćenje iste „težine”.

To learn more about all Knapsack variants — 0/1, *unbounded*, and *bounded* — see:

Contest Preparation — Knapsack and Its Variants

4. Path Counting and Combinatorial DP

The Coin Change variant that counts all ways to form an amount is an example of combinatorial dynamic programming:

we fill the array dp[x] with numbers combination
loop order matters: iterate over coins first, then amounts

This principle often appears in other problems as well - eg. when counting roads in the network (Grid DP) or counting combination of subsets. Although we don't have a separate lesson just for that yet, this idea is used in other parts of the DP section of the site, esp in scheduling and combinatorics problems.

5. Other Related DP Topics

Coin Change is a DP problem involving numbers and sums, like many problems that apply DP to arrays and strings:

DP: Longest Common Substring (LCS) – A classic string DP problem.
Problems such as Edit Distance, Grid DP, and Counting Paths use similar state-and-transition ideas.

In short: Coin Change fits into the broader family of DP issues. If you master the connections between them, you will be able to:

recognize the right DP pattern for a new problem
define the DP state and transition clearly
use 1D or 2D DP in different situations

After studying Coin Change, it is useful to explore these related topics; they build broader DP intuition and make complex problems easier to solve.

Practice Problems (Coin Change — DP)

Problem 1:

Given the coin denominations {1, 2, 5}. Determine the minimum number of coins needed to forms the sum 11.

Hint (short):
Create a DP array of dimensions dp[0..11] where dp[x] represents the minimum number of coins for amount x:


dp[0] = 0
dp[x] = min(dp[x - coin] + 1) za sve coin u {1,2,5} ako x - coin >= 0

Be careful not to use a negative index.

□ Tip:
Before viewing the solution, try to:

Think about which combinations of coins can make 11.
Estimate the minimum number of coins intuitively.

⚠ Warning:
The solution is intended for checking your work and learning. Try solving the problem on your own first.

Solution — Minimum Number of Coins

DP array for amounts 0..11 (initially +∞, except dp[0] = 0):
dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

Step by step:

Add coin 1 → dp = [0,1,2,3,4,5,6,7,8,9,10,11]
Add coin 2 → dp = [0,1,1,2,2,3,3,4,4,5,5,6]
Add coin 5 → dp = [0,1,1,2,2,1,2,2,3,3,2,3]

Answer: dp[11] = 3 (the minimum is 3 coins: 5+5+1)

C++ Implementation


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector coins = {1,2,5};
    int S = 11;
    vector dp(S+1, 1e9);
    dp[0] = 0;

    for(int x = 1; x <= S; x++) {
        for(int coin : coins) {
            if(x - coin >= 0)
                dp[x] = min(dp[x], dp[x - coin] + 1);
        }
    }

    cout << "Minimum number of coins: " << dp[S] << endl;
    return 0;
}

Problem 2:

Given the coin denominations {1, 2, 5}, determine in how many different ways the amount S = 7 can be formed. Coin order does not matter.

Hint (short):


dp[x] = number of ways to make an amount x
dp[0] = 1

Coins are processed in the outer loop to avoid counting the same combination in different orders.

For each coin, we extend the combinations already known:


for each coin:
  for x = coin .. S:
    dp[x] += dp[x - coin]

⚠ Warning:
View the solution only after attempting to solve the problem on your own.

C++ Solution (Counting the Number of Ways)


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int S = 7;
    vector coins = {1, 2, 5};

    // dp[x] = number of ways to make an amount x
    vector dp(S + 1, 0);
    dp[0] = 1; // Base case: one way to make amount 0

    // Iterate over the coins in the outer loop
    for (int coin : coins) {
        for (int x = coin; x <= S; x++) {
            dp[x] += dp[x - coin];
        }
    }

    cout << dp[S]; // Result for amount 7
    return 0;
}

The final result is stored in dp[7].

Problem 3:

The coins are given as follows:

Values: {1, 3, 4}
Usage limits: {2, 1, 1}

Determine whether it is possible to make the amount S = 6.

⚠ Warning:
This solution is intended to help you check the logic of the DP transitions.

C++ Solution (DP with Usage Limits)


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int S = 6;
    vector value = {1, 3, 4};
    vector limit = {2, 1, 1};

    int n = value.size();
    vector> dp(n + 1, vector(S + 1, false));

    dp[0][0] = true; // Amount 0 is always possible

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= S; j++) {
            dp[i][j] = dp[i - 1][j]; // Do not use coin i

            // Try using the coin k times
            for (int k = 1; k <= limit[i - 1]; k++) {
                if (j >= k * value[i - 1] &&
                    dp[i - 1][j - k * value[i - 1]]) {
                    dp[i][j] = true;
                }
            }
        }
    }

    cout << (dp[n][S] ? "YES" : "NO");
    return 0;
}

For this example, the answer is YES (combination 1 + 1 + 4).

Problem 4:

Given coins with denominations {1, 3, 4}, determine the minimum number of coins needed to make the amount S = 6.

Each coin can be used an unlimited number of times.

Hint (short):


dp[x] = the minimum number of coins for amount x
dp[0] = 0

For each amount x, we try adding one of the available coins and choose the best option.


dp[x] = min(dp[x - coin] + 1)

If no solution exists for a given amount, its value remains infinity.

⚠ Important:
Before clicking the button to show the solution, try to solve the problem on your own:

Calculate the solution by hand.
Consider whether the greedy approach always gives an optimal solution.
Fill in at least the first few values of the dp array.

This step is essential for understanding dynamic programming.

⚠ Warning:
If you have not tried solving the problem on your own, we recommend closing the solution and trying again.

C++ Solution (Minimum Number of Coins)


#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int S = 6;
    vector coins = {1, 3, 4};

    // dp[x] = the minimum number of coins for amount x
    vector dp(S + 1, INT_MAX);

    dp[0] = 0; // Base case: 0 coins are needed for amount 0

    // Calculate dp values from 1 to S
    for (int x = 1; x <= S; x++) {
        for (int coin : coins) {
            if (x >= coin && dp[x - coin] != INT_MAX) {
                dp[x] = min(dp[x], dp[x - coin] + 1);
            }
        }
    }

    if (dp[S] == INT_MAX) {
        cout << "It is not possible to make the amount";
    } else {
        cout << "Minimum number of coins: " << dp[S];
    }

    return 0;
}

For this example: 6 = 3 + 3 or 6 = 4 + 1 + 1, so the minimum number of coins is 2.

This task clearly demonstrates why the greedy algorithm does not always work, while DP produces the correct solution.

Problem 4b: Reconstructing the Solution from the DP Array

After calculating the minimum number of coins using the DP array, we often want to know exactly which coins make up the optimal solution.

The goal of this task is to determine not only the minimum number of coins, but also the specific coin values used in the solution.

The reconstruction process works as follows:

Start with the target amount S.
Find a coin coin for which: dp[S] = dp[S - coin] + 1
That coin is part of the optimal solution.
Reduce the amount and continue until reaching 0.


while S > 0:
  find a coin such that
  dp[S] = dp[S - coin] + 1
  add the coin to the solution
  S = S - coin

This procedure works because the DP array stores optimal values for smaller amounts.

⚠ Important:
Before viewing the solution:

Look at the DP array for amounts from 0 to S.
Try to trace the path backwards by hand.
Consider whether multiple optimal solutions exist.

C++ Solution with Reconstruction


#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int S = 6;
    vector coins = {1, 3, 4};

    // dp[x] = the minimum number of coins for amount x
    vector dp(S + 1, INT_MAX);
    dp[0] = 0;

    // Fill the DP array
    for (int x = 1; x <= S; x++) {
        for (int coin : coins) {
            if (x >= coin && dp[x - coin] != INT_MAX) {
                dp[x] = min(dp[x], dp[x - coin] + 1);
            }
        }
    }

    // Reconstruct the solution
    int cur = S;
    vector used;

    while (cur > 0) {
        for (int coin : coins) {
            if (cur >= coin &&
                dp[cur] == dp[cur - coin] + 1) {
                used.push_back(coin);
                cur -= coin;
                break; // Take one valid coin
            }
        }
    }

    cout << "Minimum number of coins: " << dp[S] << "\n";
    cout << "Coins that make up the solution: ";

    for (int c : used)
        cout << c << " ";

    return 0;
}

For this example, one possible output is:


Minimum number of coins: 2
Coins that make up the solution: 3 3

Note: In some cases, there may be multiple different optimal solutions, and DP reconstruction will find one of them.

Problem 4c: Reconstruction Using an Auxiliary Array

In the previous task, reconstruction was performed by directly checking the DP array. Now we will use a special array that remembers which choice led to the optimal solution.

This approach is common in practice and is also used in:

0/1 Knapsack problems
Edit distance algorithms
Shortest-path algorithms in graphs

In addition to the DP array, we introduce an array choice[x]:

dp[x] – the minimum number of coins needed for amount x
choice[x] – the value of the coin that was added last to obtain the optimal dp[x]

Whenever we find a better option:


dp[x] = dp[x - coin] + 1
choice[x] = coin

After filling the arrays, the solution can be reconstructed by simply "walking backwards".

⚠ Important:
Before viewing the solution, try to answer:

What does choice[x] represent?
Why is it enough to remember only one coin for each amount?
Does this approach discard any optimal solutions?

C++ Solution Using the `choice[]` Array


#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int S = 6;
    vector coins = {1, 3, 4};

    // dp[x] = the minimum number of coins for amount x
    vector dp(S + 1, INT_MAX);

    // choice[x] = the coin most recently added to obtain the optimal dp[x]
    vector choice(S + 1, -1);

    dp[0] = 0; // Base case

    // Fill the DP and choice arrays
    for (int x = 1; x <= S; x++) {
        for (int coin : coins) {
            if (x >= coin && dp[x - coin] != INT_MAX) {
                if (dp[x] > dp[x - coin] + 1) {
                    dp[x] = dp[x - coin] + 1;
                    choice[x] = coin; // Store the choice
                }
            }
        }
    }

    if (dp[S] == INT_MAX) {
        cout << "It is not possible to make the amount.";
        return 0;
    }

    // Reconstruct the solution
    cout << "Minimum number of coins: " << dp[S] << "\n";
    cout << "Coins in the solution: ";

    int cur = S;
    while (cur > 0) {
        cout << choice[cur] << " ";
        cur -= choice[cur];
    }

    return 0;
}

For the amount S = 6, one possible output is:


Minimum number of coins: 2
Coins in the solution: 3 3

Note: If there are multiple optimal solutions, this approach reconstructs one of them — the one found first while filling the DP array.

Problem 4d: Filling the DP Array — Visual Walkthrough

In this part, we are not writing new code. Instead, we visually track how the dp and choice arrays are filled for the minimum-coin problem.

Reminder:

Coins: {1, 3, 4}
Target amount: S = 6

Step 0 — Initial State

Amount (x)	0	1	2	3	4	5	6
dp[x]	0	∞	∞	∞	∞	∞	∞
choice[x]	-	-	-	-	-	-	-

Step 1 — Amount x = 1

We can use coin 1:


dp[1] = dp[0] + 1 = 1
choice[1] = 1

Step 2 — Amount x = 2

The best choice is to use two coins of value 1:


dp[2] = dp[1] + 1 = 2
choice[2] = 1

Step 3 — Amount x = 3

Coin 3 gives a better solution than three coins of value 1:


dp[3] = dp[0] + 1 = 1
choice[3] = 3

Step 4 — Amount x = 4

The best option is to use coin 4:


dp[4] = dp[0] + 1 = 1
choice[4] = 4

Step 5 — Amount x = 5

Possible options:

4 + 1 → 2 coins
3 + 1 + 1 → 3 coins


dp[5] = dp[4] + 1 = 2
choice[5] = 1

Step 6 — Amount x = 6

The best solution is:

3 + 3 → 2 coins


dp[6] = dp[3] + 1 = 2
choice[6] = 3

Final DP and Choice Arrays

Amount (x)	0	1	2	3	4	5	6
dp[x]	0	1	2	1	1	2	2
choice[x]	-	1	1	3	4	1	3

Reconstruction:


6 → 6 - 3 = 3
3 → 3 - 3 = 0

Solution: 3 + 3

Problem 4e: Animated DP — Highlighting Each Step

Clicking the button shows how the DP array is filled and which amount is currently being processed.

Coins: {1, 3, 4}
Target amount: 6

Initial state: dp[0] = 0. Click "Next step" to begin.

Coin Change Problem (Dynamic Programming)

Problem Definition

Why Dynamic Programming?

DP Idea and State

Bottom-Up Implementation (C++)

Time and Space Complexity

Coin Change Visualization (Minimum Number of Coins)

Coin Change Variations

1️⃣ Number of Ways to Make an Amount (Order Does Not Matter)

2️⃣ Number of Ways to Make an Amount (Order Matters)

Coin Change Visualization — Number of Ways to Make an Amount

Coin Change — Counting Ways (Visual Walkthrough)

Initializing the DP Array

Step 1: coin = 1

Step 2: coin = 2

Detaljno objašnjenje reda: dp[4] += dp[2]

Vizuelni dijagram grananja combination

Ključna intuicija

Step 3: coin = 3

Final Result

3️⃣ Limited Number of Coins

Visualization — Number of Ways (Order Matters)

Visualization — Limited Number of Coins

Greedy Algorithms — A Counterexample

An Example Where Greedy Does NOT Work

Conclusion

Greedy vs. Dynamic Programming (Visual Comparison)

Greedy Approach

Dynamic Programming (DP)

Key Difference

Intuition

Connections to Other DP Problems

1. 0/1 Knapsack Problem

2. Subset Sum Problem

3. Knapsack Variants — Unbounded and Bounded

4. Path Counting and Combinatorial DP

5. Other Related DP Topics

Practice Problems (Coin Change — DP)

Problem 1:

Hint — How to Fill the DP Array

Steps:

Solution — Minimum Number of Coins

C++ Implementation

Problem 2:

C++ Solution (Counting the Number of Ways)

Problem 3:

C++ Solution (DP with Usage Limits)

Problem 4:

C++ Solution (Minimum Number of Coins)

Problem 4b: Reconstructing the Solution from the DP Array

C++ Solution with Reconstruction

Problem 4c: Reconstruction Using an Auxiliary Array

C++ Solution Using the choice[] Array

Problem 4d: Filling the DP Array — Visual Walkthrough

Step 0 — Initial State

Step 1 — Amount x = 1

Step 2 — Amount x = 2

Step 3 — Amount x = 3

Step 4 — Amount x = 4

Step 5 — Amount x = 5

Step 6 — Amount x = 6

Final DP and Choice Arrays

Problem 4e: Animated DP — Highlighting Each Step

C++ Solution Using the `choice[]` Array