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.c

#include <stdio.h>

void print_list(int values[], int count) {
  printf("[");
  for (int i = 0; i < count; i++) {
    if (i > 0) printf(", ");
    printf("%d", values[i]);
  }
  printf("]\n");
}

int main(void) {
  int coins[] = {1, 3, 4};
  int target = 6;
  int inf = target + 1;
  int dp[7];
  for (int i = 0; i <= target; i++) dp[i] = inf;
  dp[0] = 0;
  for (int amount = 1; amount <= target; amount++) {
    for (int i = 0; i < 3; i++) {
      int coin = coins[i];
      if (amount >= coin) {
        int candidate = dp[amount - coin] + 1;
        if (candidate < dp[amount]) dp[amount] = candidate;
      }
    }
  }
  printf("%d\n", dp[target]);
  print_list(dp, 7);
  return 0;
}

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

C stores coins as stack array int coins[] = {1, 3, 4} and the DP table as fixed stack array int dp[7] for amounts 0..6.
int inf = target + 1 gives sentinel value 7; the code initializes every dp[i] to that sentinel, then sets dp[0] = 0.
The outer loop scans amount = 1..target, and the inner loop uses literal i < 3 to read coins[i]; there is no helper call or array parameter decay in the DP update itself.
When amount >= coin, the source computes candidate = dp[amount - coin] + 1 and mutates dp[amount] only if the candidate is smaller. It does not add a separate dp[...] != inf guard; the checked sentinel and target are small enough that int overflow is not a runtime concern here.
The trace records DP states from [0, 7, 7, 7, 7, 7, 7] through [0, 1, 2, 1, 1, 2, 2], with amount 6 choosing the coin 3 candidate 2.
printf("%d\n", dp[target]) prints the answer, then print_list(dp, 7) prints the full table. print_list(int values[], int count) receives the array as a pointer after parameter decay and formats each integer with printf.