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

C# DSA Implementation

basic.cs

using System;
using System.Linq;

int[] coins = {1, 3, 4};
int target = 6;
int inf = target + 1;
int[] dp = Enumerable.Repeat(inf, target + 1).ToArray();
dp[0] = 0;
for (int amount = 1; amount <= target; amount++) {
  foreach (int coin in coins) {
    if (amount >= coin) {
      int candidate = dp[amount - coin] + 1;
      if (candidate < dp[amount]) dp[amount] = candidate;
    }
  }
}
Console.WriteLine(dp[target]);
Console.WriteLine("[" + string.Join(", ", 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.

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]

Implementation notes

coins and dp are int[] arrays. Enumerable.Repeat(inf, target + 1) produces the fill sequence, and .ToArray() allocates the DP table on the managed heap, making the array GC-managed once it is no longer referenced.
The sentinel is target + 1, so dp[amount - coin] + 1 stays small for this fixture. The amount >= coin guard prevents negative indexes before the CLR's normal bounds checks on dp[...].
The outer loop scans amount from 1 to target, then tries each coin in coins order. Each int table cell is updated by value, which matches the replay frames that show the DP array after each amount is finalized.