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. @end @complexity
  • Time: O(target * coin_count)
  • Space: O(target) @end
bottom-up dynamic programming `dp[a]` is solved from already-computed smaller amounts, so every table cell has a visible dependency.

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;
?>

@end @output 2 [0, 1, 2, 1, 1, 2, 2] @end