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

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

string list_string(const vector<int>& values) {
  ostringstream out;
  out << "[";
  for (size_t i = 0; i < values.size(); i++) {
    if (i) out << ", ";
    out << values[i];
  }
  out << "]";
  return out.str();
}

int main() {
  vector<int> coins = {1, 3, 4};
  int target = 6;
  int inf = target + 1;
  vector<int> dp(target + 1, inf);
  dp[0] = 0;
  for (int amount = 1; amount <= target; amount++) {
    for (int coin : coins) {
      if (amount >= coin) {
        int candidate = dp[amount - coin] + 1;
        if (candidate < dp[amount]) dp[amount] = candidate;
      }
    }
  }
  cout << dp[target] << "\n" << 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.

Output

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

Implementation notes

In C++, coins is a std::vector<int> initialized as {1, 3, 4}, and dp is a separate std::vector<int> of length target + 1.
int inf = target + 1 gives the sentinel value 7; the code does not add a separate overflow guard because every candidate is dp[amount - coin] + 1 within this small table.
The outer loop scans amount from 1 through 6; the inner range-for copies each coin value and only reads dp[amount - coin] when amount >= coin.
Updates mutate dp[amount] in place when candidate < dp[amount]. The trace shows the table moving from [0, 7, 7, 7, 7, 7, 7] to [0, 1, 2, 1, 1, 2, 2].
list_string(const std::vector<int>&) formats the table with std::ostringstream; std::cout prints dp[target] first, then the full vector on the next line. Visible allocation is the coins vector, DP vector, and formatting buffer; visible mutation is confined to dp.