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

PHP DSA Implementation

basic.php 
<?php
function list_string($values) { return "[" . implode(", ", $values) . "]"; }
$coins = [1, 3, 4];
$target = 6;
$inf = $target + 1;
$dp = array_fill(0, $target + 1, $inf);
$dp[0] = 0;
for ($amount = 1; $amount <= $target; $amount++) {
  foreach ($coins as $coin) {
    if ($amount >= $coin) {
      $candidate = $dp[$amount - $coin] + 1;
      if ($candidate < $dp[$amount]) $dp[$amount] = $candidate;
    }
  }
}
echo $dp[$target] . PHP_EOL;
echo list_string($dp) . PHP_EOL;
?>

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

Implementation notes

  • The checked PHP values are $coins = [1, 3, 4] and $target = 6.
  • $inf = $target + 1 sets the unreachable sentinel to 7 for this run.
  • $dp = array_fill(0, $target + 1, $inf) creates seven slots, then $dp[0] = 0 gives the trace start [0, 7, 7, 7, 7, 7, 7].
  • The outer loop scans $amount from 1 through 6; the inner foreach ($coins as $coin) tries coins in 1, 3, 4 order.
  • if ($amount >= $coin) is the bounds guard before reading $dp[$amount - $coin].
  • $candidate = $dp[$amount - $coin] + 1 computes the candidate count, and if ($candidate < $dp[$amount]) writes only improvements.
  • The trace writes dp[1]=1, dp[2]=2, dp[3]=1, and dp[4]=1.
  • For amount 5, coin 1 and coin 4 both give 2, so dp[5] ends as 2.
  • For amount 6, coin 3 gives the best candidate 2, so the final table is [0, 1, 2, 1, 1, 2, 2].
  • The code does not convert the sentinel to -1; this pinned target is reachable, so echo $dp[$target] . PHP_EOL prints 2, then the full table.

Output

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