Coin Change Minimum Coins in DSA Typescript - Execution Trace

Concept Flow - Coin Change Minimum Coins

Start with amount

↓

Initialize DP array with large values

↓

Set dp[0

↓

For each coin

↓

For each amount from coin to target

↓

Update dp[amount

↓

After filling dp array

↓

If dp[target

↓

End

We build a table dp where dp[i] stores the minimum coins needed for amount i. We update dp by trying each coin for all amounts.

Execution Sample

DSA Typescript

const coins = [1, 3, 4];
const amount = 6;
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (const coin of coins) {
  for (let x = coin; x <= amount; x++) {
    dp[x] = Math.min(dp[x], dp[x - coin] + 1);
  }
}

Calculate minimum coins needed to make amount 6 using coins 1, 3, and 4.

Execution Table

Step	Operation	Amount Index (x)	Coin Used	dp[x] Before	dp[x - coin]	dp[x] After	dp Array State
1	Initialize dp	-	-	-	-	0	[0, ∞, ∞, ∞, ∞, ∞, ∞]
2	Use coin 1	1	1	∞	dp[0]=0	1	[0, 1, ∞, ∞, ∞, ∞, ∞]
3	Use coin 1	2	1	∞	dp[1]=1	2	[0, 1, 2, ∞, ∞, ∞, ∞]
4	Use coin 1	3	1	∞	dp[2]=2	3	[0, 1, 2, 3, ∞, ∞, ∞]
5	Use coin 1	4	1	∞	dp[3]=3	4	[0, 1, 2, 3, 4, ∞, ∞]
6	Use coin 1	5	1	∞	dp[4]=4	5	[0, 1, 2, 3, 4, 5, ∞]
7	Use coin 1	6	1	∞	dp[5]=5	6	[0, 1, 2, 3, 4, 5, 6]
8	Use coin 3	3	3	3	dp[0]=0	1	[0, 1, 2, 1, 4, 5, 6]
9	Use coin 3	4	3	4	dp[1]=1	2	[0, 1, 2, 1, 2, 5, 6]
10	Use coin 3	5	3	5	dp[2]=2	3	[0, 1, 2, 1, 2, 3, 6]
11	Use coin 3	6	3	6	dp[3]=1	2	[0, 1, 2, 1, 2, 3, 2]
12	Use coin 4	4	4	2	dp[0]=0	1	[0, 1, 2, 1, 1, 3, 2]
13	Use coin 4	5	4	3	dp[1]=1	2	[0, 1, 2, 1, 1, 2, 2]
14	Use coin 4	6	4	2	dp[2]=2	2	[0, 1, 2, 1, 1, 2, 2]
15	End	-	-	-	-	-	[0, 1, 2, 1, 1, 2, 2]

💡 Finished all coins and amounts; dp[6] = 2 means minimum 2 coins needed.

Variable Tracker

Variable	Start	After Step 2	After Step 8	After Step 12	Final
dp	[0, ∞, ∞, ∞, ∞, ∞, ∞]	[0, 1, 2, 3, 4, 5, 6]	[0, 1, 2, 1, 2, 3, 2]	[0, 1, 2, 1, 1, 2, 2]	[0, 1, 2, 1, 1, 2, 2]
coin	-	1	3	4	-
x (amount index)	-	1 to 6	3 to 6	4 to 6	-

Key Moments - 3 Insights

Why do we initialize dp array with Infinity except dp[0]?

We use Infinity to represent amounts not yet reachable. dp[0] = 0 means zero coins needed for amount zero. See execution_table row 1 where dp is initialized.

Why do we update dp[x] with dp[x - coin] + 1?

Because if we can make amount (x - coin) with dp[x - coin] coins, adding one coin of current coin value makes amount x. This is shown in rows 2-14 where dp[x] updates based on dp[x - coin].

Why does dp[6] end up as 2 and not a larger number?

Because using coins 3 and 3 or 4 and 2 coins, minimum coins to make 6 is 2. The dp array updates to smaller values as better combinations are found, shown in rows 11, 14, and final dp state.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is dp[3] after using coin 3?

A 3

B 1

C ∞

D 0

💡 Hint

Check the 'dp[x] After' column at step 8 for amount index 3.

At which step does dp[4] first update to 1?

A Step 12

B Step 9

C Step 5

D Step 14

💡 Hint

Look at dp array state changes in steps 9 and 12 for dp[4].

If coin 2 was added, how would dp[6] change compared to final dp?

A dp[6] would remain 2

B dp[6] would increase

C dp[6] would decrease

D dp[6] would become Infinity

💡 Hint

Adding coin 2 gives more ways to form 6 with fewer coins, so dp[6] could decrease.

Concept Snapshot

Coin Change Minimum Coins:
- Use dp array of size amount+1, fill with Infinity
- dp[0] = 0 (0 coins for amount 0)
- For each coin, update dp[x] = min(dp[x], dp[x - coin] + 1)
- dp[amount] gives minimum coins or Infinity if no solution
- Bottom-up dynamic programming approach

Full Transcript

This visualization shows how to find the minimum number of coins needed to make a target amount using given coin denominations. We create a dp array where each index represents an amount from 0 to the target. We start with dp[0] = 0 because zero coins are needed for amount zero, and all other dp values are set to Infinity to indicate unreachable amounts. Then, for each coin, we update the dp array for amounts from the coin's value up to the target. We check if using the coin reduces the number of coins needed for that amount by comparing dp[x] with dp[x - coin] + 1. After processing all coins, dp[amount] holds the minimum coins needed or Infinity if no combination is possible. The execution table traces each update step, showing how dp values improve over time. Key moments clarify why initialization uses Infinity, how updates work, and why the final dp value represents the answer. The quiz tests understanding of dp updates and effects of adding coins.