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

Fortran DSA Implementation

basic.f90

program main
  implicit none
  integer :: coins(3), dp(0:6), target, inf, amount, i, coin, candidate
  coins = [1, 3, 4]
  target = 6
  inf = target + 1
  dp = inf
  dp(0) = 0
  do amount = 1, target
    do i = 1, 3
      coin = coins(i)
      if (amount >= coin) then
        candidate = dp(amount - coin) + 1
        if (candidate < dp(amount)) dp(amount) = candidate
      end if
    end do
  end do
  print '(I0)', dp(target)
  call print_list(dp)
contains
  subroutine print_list(values)
    integer, intent(in) :: values(0:6)
    integer :: j
    write(*, '(A)', advance='no') '['
    do j = 0, 6
      if (j > 0) write(*, '(A)', advance='no') ', '
      write(*, '(I0)', advance='no') values(j)
    end do
    print '(A)', ']'
  end subroutine print_list
end program main

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.

Output

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