Dynamic programming

Dynamic programming answers a question from the answers to smaller questions of the same kind, works out each smaller answer only once and keeps it in a table. It is for "the fewest", "the most" and "how many ways" questions where trying every choice would ask the same smaller questions again and again. If you need to list every arrangement itself, use backtracking instead.

Explanation

A staircase has 4 steps, and you climb 1 or 2 steps at a time. In how many ways can you reach the top? There are 5: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.

Another way to count them is to look at the last move. It starts either from step 3, with a move of 1, or from step 2, with a move of 2. So the number of ways to reach step 4 is the number of ways to reach step 3 plus the number of ways to reach step 2. Step 1 can be reached in 1 way and step 2 in 2 ways (1+1 or 2). Then step 3 gets 2 + 1 = 3, and step 4 gets 3 + 2 = 5, the same 5 as in the list.

Fig. 1. Steps 1 and 2 are counted directly. From step 3 on, each step's number is the sum of the two numbers before it.

Paying with coins adds a choice. A country has coins worth 1, 3 and 4, as many of each as you like. Pay 6 with as few coins as possible. This time we want the best payment, not the number of payments.

At a shop counter, people take the biggest coin that fits and repeat. For 6 that is 4, then 1, then 1: three coins, the red payment in Fig. 2. But the blue payment, 3 + 3, uses two. After the 4, what is left is 2, and 2 can only be paid with two coins of 1.

Fig. 2. Circles are the amounts still to pay, and lines are coins.

Whether a first coin is good depends on how well the rest can be paid, so we try each. After the first coin, what is left is the same question for a smaller amount: 5 after a coin of 1, 3 after a coin of 3, 2 after a coin of 4. So the fewest coins for 6 is 1 plus the smallest of three numbers: the fewest coins for 5, for 3 and for 2. This rule, which gets the number for an amount from the numbers for smaller amounts, is the transition. It is the staircase idea again, with "the smallest" in place of "the sum". A recursive function does exactly this: to pay an amount, it calls itself for the amount left after each coin and keeps the best.

This plain recursion gives the right answer, 2, but in the first two levels of calls the question "pay 2" already comes up three times (Fig. 3). Each time it is computed from scratch, with all of its own calls. Paying 6 takes 24 calls, although there are only 7 different amounts to pay, from 0 to 6. Each extra unit of the amount multiplies the calls by about 1.6, and paying 40 takes 313,679,521 calls.

Fig. 3. Each circle is a call and shows the amount it pays. Each line is the coin taken. The amber circles are calls for amount 2.

So we write each value down the first time we compute it, and after that we look it up. Then each amount from 0 to 6 is computed once, and the recursion makes 14 calls instead of 24: the other calls only look up a value that is already written down. For amount 40 it makes 116 calls instead of 313,679,521.

We can even drop the recursion. Every amount needs only the values for smaller amounts, so we can fill a table from amount 0 upwards, as on the staircase. This order puts every cell after the cells it reads.

Paying 0 takes no coins. This cell is filled without reading any other, so it is the base case. Amounts 1 and 2 can only be paid with coins of 1, so they get 1 and 2. Amount 3 can start with a 1, which leaves 2 (two coins), or with a 3, which leaves 0 (no coins): the best is 1 + 0 = 1. Amount 4 is one coin of 4.

Writing the values down inside the recursion is called memoization. Filling the table in a loop, from the smallest amount up, is the other way, and the one the main code below uses. Both are dynamic programming.

Fig. 4 fills the whole table this way, from amount 0 up to 6.

Paying 0 takes no coins, so cell 0 gets 0. This is the base case.

Amount 1 can only start with a coin of 1, which leaves 0. Cell 0 holds 0, so amount 1 gets 0 + 1 = 1.

Amount 2 can only start with a coin of 1, which leaves 1. Cell 1 holds 1, so amount 2 gets 1 + 1 = 2.

Amount 3 reads cells 2 and 0, what is left after a coin of 1 or 3. They hold 2 and 0; the smallest is 0, so amount 3 gets 0 + 1 = 1.

Amount 4 reads cells 3, 1 and 0, what is left after a coin of 1, 3 or 4. They hold 1, 1 and 0; the smallest is 0, so amount 4 gets 0 + 1 = 1.

Amount 5 reads cells 4, 2 and 1, what is left after a coin of 1, 3 or 4. They hold 1, 2 and 1; the smallest is 1, so amount 5 gets 1 + 1 = 2.

Amount 6 reads cells 5, 3 and 2, what is left after a coin of 1, 3 or 4. They hold 2, 1 and 2; the smallest is 1, so amount 6 gets 1 + 1 = 2.

1/7

Fig. 4. The table for coins 1, 3 and 4, one amount per step. The outlined cells are the amounts left after each coin, and the new number is 1 plus the smallest of them.

The table now holds the fewest coins for every amount from 0 to 6, not only for 6, and each cell was filled once.

Implementation

Let's keep the table in an array f with one cell for each amount from 0 to S, the amount to pay. What one cell means is the state: f[x] is the fewest coins that pay exactly x.

The cell the problem asks for is the answer, here f[S]. With the transition, the base case and the order from above, the method is five steps:

1. State: f[x] is the fewest coins that pay exactly x. On the staircase it was the number of ways to reach step x.

2. Base case: f[0] = 0. Every other cell starts at INF, a value bigger than any real one.

3. Order: x from 1 to S, so every cell comes after the cells it reads.

4. Transition: for each coin c <= x, if f[x - c] + 1 < f[x], set f[x] = f[x - c] + 1. On the staircase it was the sum of the two cells below.

5. Answer: f[S], or -1 if it is still INF.

The first line of the input holds n, the number of coin values, and the amount S. The second line holds the n coin values. The program prints the fewest coins, then the coins themselves, using last[x]: the coin that gave f[x] its value. For the main example the input is:

3 6
1 3 4

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

const int INF = 99;  // "can't be paid"; small for the demo, use 1e9 for real inputs

int main() {
    int n, S;
    cin >> n >> S;
    vector<int> coins(n);
    for (int i = 0; i < n; i++) cin >> coins[i];

    // state: f[x] = the fewest coins that pay exactly x
    vector<int> f(S + 1, INF);
    vector<int> last(S + 1, 0);   // only needed to print the coins

    // base case: paying 0 takes no coins
    f[0] = 0;

    // order: from the smallest amount up
    for (int x = 1; x <= S; x++) {
        // transition: try each coin as the first one
        for (int c : coins) {
            if (c <= x && f[x - c] + 1 < f[x]) {
                f[x] = f[x - c] + 1;
                last[x] = c;   // only needed to print the coins
            }
        }
    }

    // answer
    if (f[S] >= INF) {
        cout << -1 << "\n";
        return 0;
    }
    cout << f[S] << "\n";

    // print the coins; remove this block if you only need their number
    for (int x = S; x > 0; x -= last[x]) {
        cout << last[x] << (x - last[x] > 0 ? ' ' : '\n');
    }
}

The table has S + 1 cells and each one tries $n$ coins, so the time is O(n \cdot S) and the memory is $O(S)$ (see time complexity).

Amounts that can't be paid

With coins 3 and 5, amount 7 can't be paid. The cells for 1, 2 and 4 are never improved by the transition, so they keep INF. Cell 7 reads cells 4 and 2, so it stays INF too, and the program prints -1.

Fig. 5. Coins 3 and 5. The outlined cells are the ones cell 7 reads.

With memoization

The array memo holds the values computed so far, and -1 means "not computed yet". The mark can't be 0, because 0 is a real value (for amount 0).

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

const int INF = 1e9;

vector<int> coins, memo;

int fewest(int x) {
    if (x == 0) return 0;                  // base case
    if (memo[x] != -1) return memo[x];     // already computed
    int best = INF;
    for (int c : coins) {                  // transition
        if (c <= x) best = min(best, fewest(x - c) + 1);
    }
    memo[x] = best;
    return best;
}

int main() {
    int n, S;
    cin >> n >> S;
    coins.resize(n);
    for (int i = 0; i < n; i++) cin >> coins[i];
    memo.assign(S + 1, -1);                // -1: not computed yet
    int ans = fewest(S);                   // answer
    cout << (ans >= INF ? -1 : ans) << "\n";
}

The first call goes down through 5, 4, 3, 2 and 1 to 0, so the amounts are finished in the order 0, 1, 2, …, 6, the same order as the loop. The time and memory are the same as the loop's.

Restoring the coins

The main program prints the coins too. last[x] is the coin that gave f[x] its value. Start at S, print last[x] and move to x - last[x], until the amount is 0. For the main example it prints 2 and then 3 3: last[6] is 3, and last[3] is 3. For amount 10 it prints 3 and 3 3 4.

Correctness proof

When the loop reaches amount $x$, every cell to its left holds the fewest coins for its amount. We show that f_x is then right too.

The value is never too small. Every value the transition writes is a real payment: a payment for x - c with f_{x-c} coins, plus the coin $c$.

The value is never too big. Take a payment for $x$ with the fewest coins, and let $c$ be its first coin. The other coins pay x - c. They are the fewest coins for x - c, because a payment for x - c with fewer coins would make the whole payment for $x$ shorter. So they are f_{x-c} coins, and the cell for x - c is already filled. The transition tries the coin $c$, so f_x \le 1 + f_{x-c}, which is the size of the best payment.

In the example, the best payment for 6 is 3 + 3 (Fig. 6). Its first coin is 3, the rest pays 3 with one coin, and f_3 = 1. The transition tries the coin 3 at amount 6 and gets 1 + 1 = 2.

Fig. 6. Cell 6 is filled from cell 3 (coin 3), and cell 3 from cell 0.

Common mistakes

• Trusting the biggest coin first, which works for coins such as 1, 2, 5, 10 but not for 1, 3, 4, as the payment of 6 shows. Fill the table instead.

• Starting every cell at 0, which makes every answer 0, since no sum of coins is smaller. Start them at INF = 1e9, as in the warning above.

• Counting with the staircase transition when the order of the coins doesn't matter, so 1+1+2, 1+2+1 and 2+1+1 count as three payments instead of one. Such a count needs a different state, shown in knapsack.

Similar algorithms

Prefer dynamic programming over backtracking when only the count or the best value is asked and many branches reach the same amount still to pay.

Greedy algorithms take the choice that looks best now and never revisit it. Use one only when you can prove that this choice never hurts later.

BFS on a state graph solves the coin problem too: the amounts are vertices, each coin is an edge, and the fewest coins for 6 is the fewest steps from 6 to 0. Dynamic programming needs no queue here, because amounts only go down, so "smaller amounts first" is a valid order. When moves can lead back to an earlier state, no order puts every state after the states it reads. For fewest steps, use BFS then.

Knapsack is the next step: each item can be used at most once, so the state needs a second number.

Practice