Dynamic programming and memoization

Why it exists

Some recursive definitions are wasteful: the same sub-question is asked again and again. The recursion for the Fibonacci numbers, $F(n) = F(n-1) + F(n-2)$, makes about $1.6^n$ calls although only $n + 1$ different values exist. Dynamic programming (DP) fixes this by answering every distinct sub-question once and remembering the answer. It turns exponential recursive algorithms into polynomial ones, and it is the standard tool for optimisation problems where a greedy rule fails (0/1 knapsack, longest common subsequence, edit distance, matrix chain multiplication, shortest paths with negative edges). GATE asks both for the method (write the recurrence, fill the table) and for the numbers (a table entry, the number of subproblems, the running time).

Prerequisites

You need recursion and the call stack (recursion and the call stack) and recurrences (solving recurrences).

Precise definitions

Optimal substructure. An optimal solution of the problem contains optimal solutions of its subproblems (so the best answer can be built from best answers of smaller problems).

Overlapping subproblems. The recursion meets the same subproblem many times, so the number of distinct subproblems is small compared with the number of recursive calls. If the subproblems do not overlap the method is divide and conquer (merge sort); if they overlap, remembering the answers pays off.

State. The few numbers that identify a subproblem (a prefix length, a capacity, a pair of indices). The set of states is the table; its size is the number of subproblems.

Recurrence. The rule that gives the answer of a state from answers of smaller states, together with the base cases.

Memoization (top-down). Write the plain recursion, but before computing a state look it up in a table, and after computing it store the result. Only the states the recursion actually reaches are computed.

Tabulation (bottom-up). Fill the table in an order in which every state's dependencies are already filled (small to large), with plain loops and no recursion.

Time. (number of states) $\times$ (work to compute one state from the smaller ones).

Space. The size of the table (often reducible: see below).

How it works

The recipe

1. Define the state and say in words what the table entry means ("$\text{dp}[i][j]$ is the cheapest path from the start to cell $(i, j)$").
2. Write the recurrence for the entry in terms of smaller entries, and the base cases.
3. Choose the filling order so that dependencies come first (a topological order of the dependency graph, which must have no cycles).
4. Read the answer from the final entry; to recover the solution itself (not only its value) remember which choice gave each entry, or trace back through the table.
5. Count states and work per state for the running time.

Fibonacci: the cost of forgetting

The three programs compute $F(n)$ by naive recursion, by recursion with a memo table, and by filling a table from the bottom. The program counts calls.

#include <stdio.h>
 
static long calls;
static long memo[64];
 
static long fib_naive(int n) {
    calls++;
    return n < 2 ? n : fib_naive(n - 1) + fib_naive(n - 2);
}
 
static long fib_memo(int n) {
    calls++;
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
}
 
static long fib_table(int n, long *steps) {
    long a = 0, b = 1;
    *steps = 0;
    for (int i = 2; i <= n; i++) {
        long c = a + b;
        a = b;
        b = c;
        (*steps)++;
    }
    return n < 2 ? n : b;
}
 
int main(void) {
    int ns[4] = {10, 20, 30, 35};
    printf("%3s %10s %12s %11s %12s\n", "n", "F(n)", "naive calls", "memo calls", "table steps");
    for (int t = 0; t < 4; t++) {
        int n = ns[t];
        long steps, v1, v2, v3, c1, c2;
        calls = 0;
        v1 = fib_naive(n);
        c1 = calls;
        for (int i = 0; i < 64; i++) memo[i] = -1;
        calls = 0;
        v2 = fib_memo(n);
        c2 = calls;
        v3 = fib_table(n, &steps);
        printf("%3d %10ld %12ld %11ld %12ld%s\n", n, v1, c1, c2, steps, (v1 == v2 && v2 == v3) ? "" : "  MISMATCH");
    }
    return 0;
}

  n       F(n)  naive calls  memo calls  table steps
 10         55          177          19            9
 20       6765        21891          39           19
 30     832040      2692537          59           29
 35    9227465     29860703          69           34

Naive recursion made $2F(n+1) - 1$ calls (about $3 \cdot 10^7$ for $n = 35$): the call tree has $F(n+1)$ leaves and repeats $F(n-2)$, $F(n-3)$, ... exponentially often, so $T(n) = T(n-1) + T(n-2) + 1 = \Theta(\varphi^n)$ with $\varphi = 1.618$. The memoised version made $2n - 1$ calls: each of the $n - 1$ values $F(2), \ldots, F(n)$ is computed once (two calls each) and the second call of each pair finds the value ready. The table version did $n - 1$ additions with no recursion at all. Both DP versions are $\Theta(n)$ in time; the memoised one uses $\Theta(n)$ stack depth plus the table, the table version only $O(1)$ if only the last two values are kept.

Memoization against tabulation

A grid example, cell by cell

A robot moves from the top left to the bottom right of a grid, one step right or down at a time, paying the cost of each cell it enters (including the first). The cheapest path: let $\text{dp}[i][j]$ be the cheapest cost to reach cell $(i, j)$. The last move into $(i, j)$ came from above or from the left, so $\text{dp}[i][j] = a[i][j] + \min(\text{dp}[i-1][j], \text{dp}[i][j-1])$, with the first row and column having only one possible predecessor and $\text{dp}[0][0] = a[0][0]$. This is optimal substructure: the best path to $(i, j)$ contains a best path to its predecessor. The same cell is a predecessor of two cells (the cell to its right and the cell below), which is the overlap.

#include <stdio.h>
 
#define R 4
#define C 5
 
int main(void) {
    int a[R][C] = {{3, 1, 4, 2, 5}, {2, 8, 1, 9, 3}, {6, 2, 3, 1, 4}, {5, 7, 2, 8, 1}};   /* cost of entering each cell */
    int dp[R][C];                                       /* dp[i][j] = cheapest path from (0, 0) to (i, j), moving right or down */
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            int best = 0;
            if (i > 0 && j > 0) best = dp[i - 1][j] < dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
            else if (i > 0) best = dp[i - 1][j];
            else if (j > 0) best = dp[i][j - 1];
            dp[i][j] = a[i][j] + best;
        }
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) printf("%4d", dp[i][j]);
        printf("\n");
    }
    printf("cheapest path from the top left to the bottom right costs %d\n", dp[R - 1][C - 1]);
    return 0;
}

   3   4   8  10  15
   5  12   9  18  18
  11  13  12  13  17
  16  20  14  21  18
cheapest path from the top left to the bottom right costs 18

Step through the filling: the grammar lists the four cases of the recurrence and the one being used is highlighted. Every cell is filled from cells that are already there.

The answer is $\text{dp}[3][4] = 18$. To recover the path, start at the end and repeatedly step back to the smaller of the two possible predecessors: the cheapest path goes right, right, down, down, right, right, down through the cells with costs $3, 1, 4, 1, 3, 1, 4, 1$ (sum $18$). There are $\binom{7}{3} = 35$ right-and-down paths in all; the program tries none of them: it does $4 \times 5 = 20$ cell computations (each $\Theta(1)$), so the time is $\Theta(RC)$ for an $R \times C$ grid, instead of the number of paths $\binom{R+C-2}{R-1}$, which is exponential. (An exhaustive check of all $35$ paths confirmed the answer $18$.)

Reducing the space

Each row of the grid table depends only on the row above it. Keeping only two rows (or one, updated in place from left to right) reduces the space from $\Theta(RC)$ to $\Theta(C)$. The price: the path can no longer be read back from the table (store the choices, or recompute). The same trick works for longest common subsequence and knapsack.

Dynamic programming against divide and conquer and greedy

• Divide and conquer: subproblems are independent, each is solved once anyway; no table is needed.
• Dynamic programming: subproblems overlap; the table makes each one cost once. All choices are tried (the $\min$ or $\max$ in the recurrence).
• Greedy: needs the extra greedy-choice property and tries only one choice (greedy method). Where it applies it is faster; where it does not, DP is the safe tool (coin change with $\{1, 3, 4\}$).

Pseudo-polynomial time. Knapsack with capacity $W$ takes $\Theta(nW)$ time, polynomial in the value $W$ but exponential in the number of bits of $W$ (analysing loops); such algorithms are called pseudo-polynomial.

Worked examples

Cheat box

Traps and GATE patterns

Connections

DP contrasts with divide and conquer (no overlap) and with the greedy method (one choice). Its standard applications are in LCS, edit distance, knapsack and matrix chain and LIS and coin change; the shortest-path DP of Floyd-Warshall and Bellman-Ford follow the same pattern. The recurrences are those of solving recurrences; the stack depth of memoisation is that of recursion.

PYQs

Consider a table T, where the elements T[i][j],
0 <= i, j <= n, represent the cost of the optimal
solutions of different subproblems of a problem
that is being solved using a dynamic
programming algorithm. The recursive
formulation to compute the table entries is as
follows:
T[0][k] = T[k][0] = 1
for k = 0, 1, 2, ..., n

T[i][j] = 2T[i-1][j]+3T[i][j-1] for 1 ≤ i, j ≤ n

Consider the following two algorithms to
compute entries of T. Assume that for both the
algorithms, for all 0 ≤ i, j ≤ n, T[i][j] has been
initialized to 1.
Algorithm B1:
For i = 1 to n
For j = 1 to n
T[i][j] = 2T[i - 1][j] + 3T[i][j - 1]
Algorithm B2:
For s = 2 to 2n
For i = 1 to n
For j = 1 to n
If (i + j == s)
T[i][j] = 2T[i - 1][j] + 3T[i][j - 1]

Algorithm Bk, k ∈ {1, 2}, is said to be correct if
and only if it calculates the correct values of
T[i][j], for all 0 ≤ i, j ≤ n, as per the recursive
formulation, at the end of the execution of the
algorithm Bk.
Which one of the following statements is true?

Consider the following table:

Algorithms
Design
Paradigms
P
Kruskal
i
Divide and
Conquer
Q
Quicksort
ii
Greedy
R
Floyd-
Warshall
iii Dynamic
Programming

Given below are some algorithms, and some
algorithm design paradigms.
List - I
P. Dijkstra's Shortest Path
Q. Floyd-Warshall algorithm to compute all
pairs shortest path
R. Binary search on a sorted array
S. Backtracking search on a graph
List – II
i. Divide and Conquer
ii. Dynamic Programming
iii. Greedy design
iv. Depth-first search
v. Breadth-first search
Match the above algorithms on the left to the
corresponding design paradigm they follow.

Match the following:

(P) Prim's algorithm for
minimum spanning tree
(i) Backtracking
(Q) Floyd-Warshall
algorithm for all pairs
shortest paths
(ii) Greedy
method
(R) Mergesort
(iii) Dynamic
programming
(S) Hamiltonian circuit
(iv) Divide and
conquer

Self-check

Revision card

References