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

JavaScript DSA Implementation

basic.js 
function listString(values) { 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

  • JavaScript stores coins and dp as Array objects containing Number values. The unreachable sentinel is the finite value target + 1, so this checked-in run uses 7 rather than Infinity.
  • Array(target + 1).fill(inf) initializes every slot to 7, then dp[0] = 0 seeds the base case. The algorithm mutates the same dp array in place.
  • The outer loop scans amount from 1 through target; the inner for...of loop tries coins [1, 3, 4] in that order. amount >= coin guards the lookup dp[amount - coin].
  • Candidates are numeric additions, dp[amount - coin] + 1, and the update is an explicit minimum check: if (candidate < dp[amount]) dp[amount] = candidate.
  • The replayed table states are [0, 7, 7, 7, 7, 7, 7], then [0, 1, 7, 7, 7, 7, 7], [0, 1, 2, 7, 7, 7, 7], [0, 1, 2, 1, 7, 7, 7], [0, 1, 2, 1, 1, 7, 7], [0, 1, 2, 1, 1, 2, 7], and [0, 1, 2, 1, 1, 2, 2].
  • console.log(dp[target]) prints 2, then listString(dp) prints the final table. Visible allocation is the coins array, DP array, and output strings; the nested loops only update scalar bindings and DP slots.