Dynamic programming

Introduction

The plain recursive Fibonacci, fib(n) = fib(n-1) + fib(n-2), is very slow: fib(40) makes over 300 million calls, because it works out the same values again and again. Dynamic programming (DP) fixes this: solve each smaller problem once, store the answer, and look it up next time.

DP works when a problem has:

• overlapping subproblems: the same smaller problems come up many times;
• optimal substructure: the best answer is built from the best answers to smaller problems.

Dynamic programming sounds grand, but the idea is plain: never work out the same thing twice. That one idea turns many exponential searches into small tables.

How it works

Tabulation: bottom up

#include <stdio.h>
#define INF 1000000

int main(void) {
    int coins[] = {1, 3, 4};
    int amount = 6;
    int best[7];   // best[x] = the fewest coins that make x
    best[0] = 0;
    for (int x = 1; x <= amount; x++) {
        best[x] = INF;
        for (int c = 0; c < 3; c++)
            if (coins[c] <= x && best[x - coins[c]] + 1 < best[x])
                best[x] = best[x - coins[c]] + 1;
    }
    printf("fewest coins for %d: %d\n", amount, best[amount]);
    return 0;
}

The coin problem greedy got wrong: the fewest coins from 4 that make 6. Let best[x] be the fewest coins that make x. The last coin used is some coin c, and what is left, x - c, must also be made with the fewest coins. So:

best[0] = 0
best[x] = 1 + the smallest best[x - c], over every coin c <= x

Fill the table from x = 1 upwards; every value it needs is already there. Watch best fill: best[6] comes out as 2 (3 + 3). With k coins and amount A, it is O(k × A).

How to design a DP

1. Define the subproblem in words: "best[x] = fewest coins that make x".
2. Write the recurrence: how an answer is built from smaller answers.
3. Set the base cases: best[0] = 0.
4. Choose an order so every value is ready before it is needed.
5. Read off the answer: best[amount].

Syntax

long long memo[N];              // zero means not known yet

if (memo[n] != 0) return memo[n];
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];

Example

#include <stdio.h>

long long memo[13];   // 0 means "not worked out yet"

long long fib(int n) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];   // already known
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main(void) {
    printf("fib(12) = %lld\n", fib(12));
    return 0;
}

Keep the recursion, but remember results in memo. Before computing fib(n), check whether memo[n] already holds it. Each value from 2 to n is computed once, so it is O(n) instead of O(2ⁿ): fib(12) makes 23 calls here, against 465 for the plain version. Watch memo fill from the bottom up as the calls return. The table holds long long because Fibonacci numbers grow fast: fib(50), about 12.6 billion, does not fit in an int.

Line by line

1. memo is a global array, so C sets every cell to 0, which here means "not worked out yet".
2. fib first handles the base cases: fib(0) is 0 and fib(1) is 1.
3. If memo[n] is not 0, the answer is already known, and it returns at once.
4. Otherwise it computes the value from two smaller calls and stores it before returning.
5. The type is long long so that larger values do not overflow.
6. main prints fib(12), which is 144.

Expected result

fib(12) = 144

In the real world

Spell checkers measure how close two words are with a DP table. Route planners, gene comparison and the Viterbi method used in speech recognition and error-correcting codes are all dynamic programs.

Common mistakes

• Using 0 as "not computed" when 0 can be a real answer: use -1 instead.
• Filling a table in an order that reads cells not yet computed.
• Starting to code before writing what each cell means.

Best practices

• Write the meaning of a table cell as a comment above the table.
• Test the recurrence by hand on the smallest few inputs.
• Check the largest possible answer and pick an integer type that holds it.

Summary

Dynamic programming stores the answers to overlapping subproblems so that each is solved once. It can run top down with memoization or bottom up with a table, and it starts from a clear definition of the subproblem.

Mark lesson complete