Coin Change (Bottom-Up)

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

Algorithm

Steps

Initialize dp[0] = 0 and all other amounts to an unreachable sentinel.
Scan amounts from 1 through 6.
For each coin, read the earlier cell dp[amount - coin] when it exists.
Write the smallest candidate into the current amount.
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

Perl DSA Implementation

basic.pl

use strict;
use warnings;

sub list_string { return "[" . join(", ", @_) . "]"; }

my @coins = (1, 3, 4);
my $target = 6;
my $inf = $target + 1;
my @dp = (($inf) x ($target + 1));
$dp[0] = 0;
for my $amount (1..$target) {
  for my $coin (@coins) {
    if ($amount >= $coin) {
      my $candidate = $dp[$amount - $coin] + 1;
      $dp[$amount] = $candidate if $candidate < $dp[$amount];
    }
  }
}
print "$dp[$target]\n";
print list_string(@dp) . "\n";

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.

Step 2 - Early amounts become reachable

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

Step 3 - Final answer at amount 6

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

Implementation notes

my @coins = (1, 3, 4) stores the pinned coin values in a Perl array with the @ sigil.
my $target = 6 is the amount being solved, and my $inf = $target + 1 makes the sentinel value 7.
my @dp = (($inf) x ($target + 1)) fills seven Perl array slots with 7.
$dp[0] = 0 marks amount 0 as needing zero coins.
Unlike the Lua version, this Perl source uses the amount itself as the zero-based array index: amount a lives at $dp[$a].
The outer loop is for my $amount (1..$target), so amounts are solved in order from 1 to 6.
The inner loop is for my $coin (@coins), trying coins 1, 3, then 4 for each amount.
if ($amount >= $coin) guards the table read so the code only looks at a non-negative earlier amount.
The candidate expression is $dp[$amount - $coin] + 1.
The update is conditional: $dp[$amount] = $candidate if $candidate < $dp[$amount].

DP replay

init: [0, 7, 7, 7, 7, 7, 7]
a=1: coin 1 -> [0, 1, 7, 7, 7, 7, 7]
a=2: coin 1 -> [0, 1, 2, 7, 7, 7, 7]
a=3: coin 3 improves to 1 -> [0, 1, 2, 1, 7, 7, 7]
a=4: coin 4 improves to 1 -> [0, 1, 2, 1, 1, 7, 7]
a=5: best is 2 -> [0, 1, 2, 1, 1, 2, 7]
a=6: coin 3 gives 2 -> [0, 1, 2, 1, 1, 2, 2]

The final answer is $dp[$target], so this run prints 2.
list_string(@dp) joins the DP array with ", ", and the second print emits [0, 1, 2, 1, 1, 2, 2].

Output

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