Recursion and Dynamic Programming

Coin Change (Bottom-Up)

Build a one-dimensional table where each amount stores the fewest coins needed to make it.

Algorithm

Steps

  1. Initialize dp[0] = 0 and all other amounts to an unreachable sentinel.
  2. Scan amounts from 1 through 6.
  3. For each coin, read the earlier cell dp[amount - coin] when it exists.
  4. Write the smallest candidate into the current amount.
  5. Print both the final answer and the full DP array.

Complexity

  • Time: O(target * coin_count)
  • Space: O(target)
bottom-up dynamic programming `dp[a]` is solved from already-computed smaller amounts, so every table cell has a visible dependency.

Visual walkthrough

TypeScript DSA Implementation

basic.ts 
function listString(values: number[]): string { return `[${values.join(", ")}]`; }
const coins = [1, 3, 4];
const target = 6;
const inf = target + 1;
const dp = Array(target + 1).fill(inf);
dp[0] = 0;
for (let amount = 1; amount <= target; amount++) {
  for (const coin of coins) {
    if (amount >= coin) {
      const candidate = dp[amount - coin] + 1;
      if (candidate < dp[amount]) dp[amount] = candidate;
    }
  }
}
console.log(dp[target]);
console.log(listString(dp));

The pinned coins are [1, 3, 4] and target is 6. The diagrams show the one-dimensional DP table becoming reachable from left to right.

Step 1 - Initialize reachable amount 0

dp[0] = 0; every other amount starts as the sentinel 7.

Initial DP table for target 6.a0a1a2a3a4a5a60777777

Step 2 - Early amounts become reachable

With coins 1, 3, and 4, amounts 1 through 4 fill as [1, 2, 1, 1].

Table after filling amounts 1 through 4.a0a1a2a3a4a5a60121177base11+134todotodo

Step 3 - Final answer at amount 6

dp[5] = 2 and dp[6] = 2, so the target needs two coins.

Final DP table: [0, 1, 2, 1, 1, 2, 2].a0a1a2a3a4a5a6012112211+1341+43+3

Output

2
[0, 1, 2, 1, 1, 2, 2]

Implementation notes

  • In TypeScript, coins is inferred as number[] from [1, 3, 4] and target is the numeric literal 6. The checked source uses Array(target + 1).fill(inf), so dp is inferred from the bare Array constructor rather than an explicit number[] annotation.
  • inf is target + 1, so Array(target + 1).fill(inf) creates seven slots initialized to sentinel 7, then dp[0] = 0 mutates the base case.
  • The outer loop advances amount from 1 through 6; the inner for (const coin of coins) only reads dp[amount - coin] when amount >= coin.
  • Updates use const candidate = dp[amount - coin] + 1 and an explicit candidate < dp[amount] comparison rather than Math.min.
  • The trace records table mutations from [0, 7, 7, 7, 7, 7, 7] through [0, 1, 2, 1, 1, 2, 2], with amount 6 writing dp[6] = 2 from coin 3.
  • The two console.log calls print 2 and the full table string. Visible allocation is the coins array literal, the DP array, and the output string; mutation is limited to numeric dp cells.