Dynamic Programming 1: Memoization, Tabulation and Recognizing Subproblems

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

The definition of the Fibonacci numbers is one line: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). We translate it straight into code and count how many times it is called:

public static long Calls;

// O(2^n): the same subproblems are solved again and again.
public static long Naive(int n)
{
    Calls++;
    return n < 2 ? n : Naive(n - 1) + Naive(n - 2);
}

F(40) = 102,334,155. How many times is Naive called to compute it? A few hundred, a few thousand, a few million? And think about this too: what do you need to add to the code to do the same computation with 79 calls?

Overlapping Subproblems and Optimal Substructure

The answer from a real run:

fib(20) = 6,765: naive calls=21,891 (0.0 ms), memo calls=39
fib(30) = 832,040: naive calls=2,692,537 (3.3 ms), memo calls=59
fib(40) = 102,334,155: naive calls=331,160,281 (325.8 ms), memo calls=79

331 million calls. The reason is in the recursion tree: F(40) calls F(39) and F(38); F(39) calls F(38) once more. F(38) is computed twice, F(37) three times, F(36) five times; the repetition counts themselves follow the Fibonacci sequence and grow exponentially. Yet there are only 41 distinct subproblems: F(0) to F(40).

DP (Dynamic Programming) is a technique built on these two observations. Overlapping subproblems: the same subproblems come up again and again, so solving each once and storing the result pays off. Optimal substructure: the answer to the big problem can be built from the answers to the subproblems. In the 20th post of the series greedy needed optimal substructure too; the difference is that greedy trusts a single subproblem at each step and ignores the rest, while DP knows the answers to all subproblems and chooses among them. The "programming" in the name is not computer programming but, in the sense Richard Bellman used it in the 1950s, "planning by filling in a table".

Fibonacci: From Exponential to O(1) Memory

The first step is memoization (top-down): write the same recursive code, but look in a cache before computing a result and write to the cache after computing it.

// Top-down: same recursion, each n computed once. O(n) time, O(n) memory + O(n) stack.
public static long Memo(int n) => Memo(n, new long?[n + 1]);

private static long Memo(int n, long?[] memo)
{
    Calls++;
    if (n < 2) return n;
    return memo[n] ??= Memo(n - 1, memo) + Memo(n - 2, memo);
}

The ??= operator reduces the work to one line: if memo[n] is null it computes the right-hand side and stores it, otherwise it returns the stored value. We can use an array instead of a Dictionary for the cache because the state is a single small integer. The call count drops from 331 million to 79: at most two calls per n.

The second step is tabulation (bottom-up): drop recursion entirely and fill the table from small to large. When each F(i) is computed, the F(i-1) and F(i-2) it needs are already in the table.

// Bottom-up: fill the table from small to large. No recursion.
public static long Table(int n)
{
    if (n < 2) return n;
    long[] f = new long[n + 1];
    f[1] = 1;
    for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
    return f[n];
}

The third step is to look at what the table is really needed for: each step uses only the last two values. The rest of the table is garbage.

// Only the last two values are needed: O(1) memory.
public static long Iterative(int n)
{
    long prev = 0, current = 1;
    if (n == 0) return 0;
    for (int i = 2; i <= n; i++) (prev, current) = (current, prev + current);
    return current;
}

I measured the four versions for n = 30 with BenchmarkDotNet. The measurements were taken on an Apple M5 (10 cores), macOS 27.0.1, .NET 10.0.13 and BenchmarkDotNet 0.15.8. I ran the benchmarks one at a time, but other work was running on the machine; look at the ratios, not the absolute numbers.

| Method    | N  | Mean             | Ratio | Allocated |
|---------- |--- |-----------------:|------:|----------:|
| Naive     | 30 | 2,100,447.155 ns | 1.001 |         - |
| Memo      | 30 |       100.982 ns | 0.000 |     520 B |
| Table     | 30 |        26.285 ns | 0.000 |     272 B |
| Iterative | 30 |         7.370 ns | 0.000 |         - |

Naive 2.1 ms, memoization 101 ns: about 20,000 times. The 4x difference between memo and table is the price of recursion and of the long? array (an extra bool plus alignment per nullable slot, 520 bytes for 31 slots). The iterative version does not allocate and finishes in 7 ns. The 0.000 in the Ratio column is because the ratio is too small to fit in three decimals. These four steps are a path you can follow in almost every DP problem: first a correct recursive definition, then memoization, then a table, then only the part of the table that is really needed.

A Five-Step Recipe

When you look at a new problem with DP in mind, answer these five questions in order:

• State: what is the smallest piece of information that defines a subproblem on its own? In Fibonacci, n; in making change, the remaining amount.
• Transition: how is a state's answer built from the answers of smaller states? F(n) = F(n-1) + F(n-2).
• Base case: which states end the recursion with an answer known directly? F(0) = 0, F(1) = 1.
• Computation order: in what order must you fill the table so that every state's needed answers are ready? From small n to large.
• Answer: which cell of the table answers the actual question? f[n].

Choosing the state correctly is the hardest part and where most bugs are. We will read each of the examples below through these five steps.

Climbing Stairs and House Robber

Climbing stairs: in how many different ways can you climb a staircase of n steps, going up 1 or 2 steps at a time? State: which step we are on. Transition: step i is reached either from i-1 or from i-2, so ways(i) = ways(i-1) + ways(i-2). Base case: ways(0) = ways(1) = 1. It is Fibonacci in disguise; the same O(1) memory technique:

// ways[i] = ways[i-1] + ways[i-2]
public static long ClimbStairs(int n)
{
    long a = 1, b = 1; // ways(0), ways(1)
    for (int i = 2; i <= n; i++) (a, b) = (b, a + b);
    return b;
}

House robber in Bookstore clothing: on a campaign calendar we cannot put discounts on consecutive days (two discount days in a row train customers to wait for discounts), and each day has a different expected extra revenue. Maximize total revenue by choosing non-consecutive days. State: the first i days. Transition: either we do not pick day i (the answer is that of the first i-1 days), or we pick it (the answer of the first i-2 days plus today's revenue); best(i) = max(best(i-1), best(i-2) + value(i)).

// best[i] = max(best[i-1], best[i-2] + value[i])
public static int HouseRobber(int[] values)
{
    int skip = 0, take = 0; // best up to the previous item without / with it
    foreach (int v in values)
    {
        (skip, take) = (Math.Max(skip, take), skip + v);
    }

    return Math.Max(skip, take);
}

house robber [2,7,9,3,1]: 12

The answer is 12: days 1, 3 and 5 (2 + 9 + 1). A greedy that picks the largest single value 9 and drops its neighbors also finds 12 here, but on a sequence like [2, 7, 9, 8] greedy finds 9 + 2 = 11 while DP finds 7 + 8 = 15 (that case is in the tests too). I leave the greedy side to the small experiment.

Coin Change: Fewest Coins and Number of Ways

Let's solve the problem where greedy failed in the previous post with DP. Fewest coins: the state is the remaining amount, the transition is "if the last coin you gave is c, you must have given amount a - c in the best way", i.e. best(a) = min(best(a - c) + 1).

// best[a] = min over coins c of best[a - c] + 1; -1 when the amount cannot be made.
public static int MinCoins(int[] coins, int amount)
{
    int[] best = new int[amount + 1];
    Array.Fill(best, int.MaxValue);
    best[0] = 0;
    for (int a = 1; a <= amount; a++)
    {
        foreach (int c in coins)
        {
            if (c <= a && best[a - c] != int.MaxValue)
            {
                best[a] = Math.Min(best[a], best[a - c] + 1);
            }
        }
    }

    return best[amount] == int.MaxValue ? -1 : best[amount];
}

min coins {1,3,4} -> 6: 2

The cost is O(amount × number of coins). 2 (3 + 3) where greedy gave 3 coins. Since we use int.MaxValue to mean "cannot be made", we check first so that best[a - c] + 1 does not overflow.

Number of ways: in how many different ways can you make 5 units with coins of 1, 2 and 5? Here lies one of the sneakiest DP traps: the order of the two loops. If the coins are in the outer loop, each coin is "unlocked" in turn and 1 + 2 + 2 and 2 + 1 + 2 are counted once as the same combination. If the amount is in the outer loop, every amount can be reached from every coin and orderings are counted separately:

// Number of combinations (order does not matter): coins in the OUTER loop.
public static long CountWays(int[] coins, int amount)
{
    long[] ways = new long[amount + 1];
    ways[0] = 1;
    foreach (int c in coins)
        for (int a = c; a <= amount; a++)
            ways[a] += ways[a - c];
    return ways[amount];
}

// Swapped loops count ordered sequences (1+2 and 2+1 twice) - a different question.
public static long CountSequences(int[] coins, int amount)
{
    long[] ways = new long[amount + 1];
    ways[0] = 1;
    for (int a = 1; a <= amount; a++)
        foreach (int c in coins)
            if (c <= a) ways[a] += ways[a - c];
    return ways[amount];
}

ways {1,2,5} -> 5: combinations=4, sequences=9

4 combinations: 5, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1. The 9 ordered sequences answer a different question: "in what order can I put the coins into the till". Both are valid DP; the problem statement says which one is wanted, and the code changes by the position of a single line. The tests pin down both:

[Fact]
public void CountWays_CountsCombinationsNotSequences()
{
    Assert.Equal(4, DynamicProgramming.CountWays([1, 2, 5], 5));
    Assert.Equal(9, DynamicProgramming.CountSequences([1, 2, 5], 5));
}

Test run summary: Passed!
  total: 17
  failed: 0
  succeeded: 17
  skipped: 0
  duration: 347ms

Top-Down or Bottom-Up

The advantage of memoization is that it is easy to write: you code the recursive definition as it is and add a cache. It computes only the states actually needed; if the state space is large but a small part of it is enough for the answer, that is a significant gain. The disadvantage is recursion: every call is a stack frame, and the depth is the length of the state chain. I called Fibonacci with memoization for n = 1,000,000:

public static void Overflow() => Console.WriteLine(Fibonacci.Memo(1_000_000));

Stack overflow.
Repeated 104510 times:
--------------------------------
   at Algorithms.Paradigms.Fibonacci.Memo(Int32, System.Nullable`1<Int64>[])
--------------------------------
   at Algorithms.Paradigms.Fibonacci.Memo(Int32)
   at Demo21.Overflow()
   at Program.<Main>$(System.String[])

The process died with exit code 134; as we saw in the 5th post of the series, a StackOverflowException cannot be caught. About 104,500 frames fit into the default stack on this machine (the number depends on the stack size and the frame size). The warning is not specific to Fibonacci: any top-down DP hits the same wall when the state chain is long (for example a memoization advancing character by character over a long string).

Tabulation's advantages are the opposite: no recursion, no stack depth problem, cache-friendly loops, and open to memory optimizations like keeping only the needed part of the table (O(1) Fibonacci, two-row knapsack). The disadvantage is that you have to find the computation order yourself, and it sometimes computes states that are never used. A practical rule: write top-down first, pin down its correctness with tests, then convert to bottom-up if performance or depth requires it, and test the two versions against each other.

Production Notes

Overflow and number types. F(92) is the last Fibonacci number that fits in a long, F(93) does not; "number of ways" counts grow very quickly too. That is why F(90) was chosen in the test. For large counts use a checked context (an exception on overflow), UInt128 or BigInteger; or if the problem asks for something like "modulo 10⁹+7", take the modulo on every addition.

The memo's lifetime. Keeping memoization results in a static dictionary (a cache that lives as long as the application) looks tempting at first, but it can turn into a memory leak and it is not thread-safe. Our Memo creates its cache anew on every call. If you need a cache shared across the application, use a real cache with a size limit and expiration; we covered the cache options in ASP.NET Core in the related series.

Calculate the state size. The table is as big as the number of states. A change-making problem with an amount of 10⁹ needs O(amount) memory, which means a 4 GB int[]; in that case DP may not be the right tool, or the state needs to be redefined.

Static counters and parallel tests. Fibonacci.Calls in this post is a static counter for demonstration; since xUnit runs test classes in parallel, if two tests increment the same counter the asserts break at random. If you use a counter for measurement, move it to an instance or a parameter.

Common Pitfalls

Designing the memo key wrong. Let's write the number-of-ways problem top-down: the state is (remaining amount, the coin from which I may still use coins). I compared it with a version whose cache key is the amount alone:

long Ways(int amount, int index, Dictionary<(int, int), long> memo)
{
    if (amount == 0) return 1;
    if (amount < 0 || index == coins.Length) return 0;
    if (memo.TryGetValue((amount, index), out long cached)) return cached;
    long result = Ways(amount - coins[index], index, memo)   // use coins[index] again
                + Ways(amount, index + 1, memo);             // never use coins[index]
    return memo[(amount, index)] = result;
}

long WaysWrongKey(int amount, int index, Dictionary<int, long> memo)
{
    if (amount == 0) return 1;
    if (amount < 0 || index == coins.Length) return 0;
    if (memo.TryGetValue(amount, out long cached)) return cached; // BUG: ignores index
    long result = WaysWrongKey(amount - coins[index], index, memo)
                + WaysWrongKey(amount, index + 1, memo);
    return memo[amount] = result;
}

top-down ways, key=(amount,index): 4
top-down ways, key=amount only:    9

The wrong-key version confuses the answer to "3 units, starting from the 2-unit coin" with the answer to "3 units, starting from the 1-unit coin" and says 9. No exception, and the result looks plausible. The rule: the cache key must be all the parameters that affect the function's result. If a memoized function's result depends on a parameter that is not in the key, the cache gives wrong answers.

Recursion depth in a top-down solution. We saw it above; on a large input the process dies and it cannot be caught. The depth is determined by the length of the state chain, not the input size; if a long chain is possible, switch to bottom-up.

Forgetting or misplacing base cases. ways[0] = 1 ("there is one way to give 0 units: give nothing") can feel counterintuitive, but if you make it 0 the whole table comes out zero. Compute the base case by hand for the smallest few inputs and pin it down with a test.

Assuming loop order does not matter. The only difference between CountWays and CountSequences is the position of two lines, and the answers are 4 and 9. In table filling, the order is part of the state definition.

A Small Experiment

★☆☆ Run HouseRobber with [2, 7, 9, 8], then write the greedy "pick the largest value, drop its neighbors, repeat" and compare the results. Count how often greedy is wrong on 1,000 random sequences.

★★☆ Extend MinCoins to also return which coins were used: keep the last coin used for each amount in a separate array and reconstruct [3, 3] for 6.

★★★ Run memoized Fibonacci for large n without the depth problem: first limit the recursion depth by "warming up" the memo from small to large n (calling F(1000), F(2000), ... in turn), then verify the same result with BigInteger and tabulation. How many digits does F(10,000) have?

In this post we worked with one-dimensional states: a number, an amount, a day. In the next and final post of the series the state grows to two dimensions: the prefixes of two strings, a budget and an item count. "Did you mean?" with edit distance, diffs with LCS (Longest Common Subsequence) and a campaign budget with 0/1 knapsack; after that we will gather the patterns we saw throughout the series into a decision table.