Step 2 of 6
Bottom-up tables and coin change
Memoization works top-down: start from the big question and recurse, caching as you go. The other way to do DP is bottom-up (also called tabulation): fill the table starting from the smallest questions, in an order where everything an entry needs is already filled in. No recursion at all, so there's no risk of running out of stack, and it's usually a bit faster.
For Fibonacci, bottom-up is a simple loop: f[0] = 0; f[1] = 1; then f[i] = f[i - 1] + f[i - 2] for i from 2 up.
When greedy fails
Paying an amount with as few coins as possible sounds easy: take the biggest coin that fits, repeat. With euro or dollar coins that "greedy" rule happens to be optimal. With coins 1, 3 and 4 and an amount of 6, greedy takes 4 + 1 + 1 (three coins), but 3 + 3 uses two. Greedy commits to a choice without checking what it costs later. DP checks every option, but only once per amount.
This program shows greedy's answer, then builds a bottom-up table for a related question: in how many different ways can each amount be made?
#include <iostream>
#include <vector>
int greedy(const std::vector<int>& biggest_first, int amount) {
int count = 0;
for (int c : biggest_first)
while (amount >= c) {
amount -= c;
count++;
}
return count;
}
int main() {
std::vector<int> coins = {1, 3, 4};
int amount = 6;
std::cout << "greedy uses " << greedy({4, 3, 1}, amount) << " coins\n";
// ways[a] = how many different coin combinations make the amount a
std::vector<long long> ways(amount + 1, 0);
ways[0] = 1; // one way to make 0: use no coins
for (int c : coins) // coins in the outer loop: combinations, not orderings
for (int a = c; a <= amount; a++)
ways[a] += ways[a - c];
for (int a = 0; a <= amount; a++) std::cout << ways[a] << " ";
std::cout << "\n";
}
greedy uses 3 coins
1 1 1 2 3 3 4
How it works
ways[0] = 1is the base case: the empty combination.- Processing one coin at a time,
ways[a] += ways[a - c]adds every combination fora - cwith one more coincon top. Because each coin is fully processed before the next, a combination like 1 + 3 is counted once, not also as 3 + 1. - Amount 6 can be made 4 ways: 1+1+1+1+1+1, 1+1+1+3, 1+1+4 and 3+3.
The fewest coins
Minimum coins uses the same table shape with a different rule. Let best[a] be the fewest coins that make a. The last coin used is one of the coins c, and before it you had a - c, made in best[a - c] coins. So:
best[0] = 0
best[a] = 1 + (the smallest best[a - c] over every coin c <= a that can be made)
Fill best for a = 1, 2, 3, ... in order, so every best[a - c] is ready when it's needed. Amounts that can't be made (like 3 with only 2-coins) need a marker meaning "impossible", such as a very large number, that must never win the "smallest" comparison or be added to.
Your turn: write min_coins(coins, amount), returning the fewest coins that add up to amount (each coin value can be used any number of times), or -1 if it can't be done.