Dynamic programming: the idea

Dynamic programming (DP) is for problems where a recursive solution keeps solving the same smaller problems again and again. Instead of recomputing them, DP solves each one once and stores the answer. It often turns an exponential algorithm into a polynomial one. The name is historical and slightly misleading; “clever recursion with a cache” is closer.

Two signs that DP applies

• Optimal substructure: the answer to the problem can be built from answers to smaller versions of the same problem.
• Overlapping subproblems: those smaller problems are needed many times. (In merge sort they are not: each half is sorted once. That is divide and conquer, not DP.)

Example: climbing stairs

You climb n steps, taking 1 or 2 at a time. How many different ways are there? Think about the last move: you arrived either from step n − 1 (a single step) or from step n − 2 (a double step). So ways(n) = ways(n − 1) + ways(n − 2), with ways(0) = ways(1) = 1. Written as plain recursion this is the Fibonacci tree from the recursion lesson: about 1.6ⁿ calls.

Top-down: memoisation

Keep the recursive code, but store each answer in a dictionary or array the first time it is computed. Every n is computed once: O(n).

Bottom-up: tabulation

Or skip recursion entirely: fill an array from the smallest cases upwards, so that every value you need is already there. No recursion means no stack overflow, and often the table can be shrunk: here only the last two values are ever needed.

1var memo = new Dictionary<int, long>();2Console.WriteLine(WaysMemo(50));3Console.WriteLine(WaysTable(50));4Console.WriteLine(WaysTwoVariables(50));5 6long WaysMemo(int n)                               // top-down7{8    if (n <= 1) return 1;9    if (memo.TryGetValue(n, out long known)) return known;10    return memo[n] = WaysMemo(n - 1) + WaysMemo(n - 2);11}12 13static long WaysTable(int n)                       // bottom-up14{15    var ways = new long[n + 1];16    ways[0] = 1;17    ways[1] = 1;18    for (int i = 2; i <= n; i++)19        ways[i] = ways[i - 1] + ways[i - 2];20    return ways[n];21}22 23static long WaysTwoVariables(int n)                // bottom-up, O(1) memory24{25    long prev = 1, cur = 1;26    for (int i = 2; i <= n; i++)27        (prev, cur) = (cur, prev + cur);28    return cur;29}

20365011074
20365011074
20365011074

The plain recursion for n = 50 would make about 40 billion calls. The DP versions do 49 additions.

The DP recipe

1. Define the state: what does one subproblem mean? (“ways[i] = number of ways to reach step i”, “best[a] = fewest coins for amount a”).
2. Find the recurrence: how is a state built from smaller states? Thinking about the *last* decision usually works.
3. Base cases: the smallest states, answered directly.
4. Order: compute states so that dependencies are ready (usually increasing size).
5. Answer: which state (or combination) is the final answer?

Fewest coins, done right

The greedy lesson showed that “biggest coin first” fails for coins 1, 3 and 4. DP considers every possible last coin: best[a] = 1 + min(best[a − c]) over all coins c ≤ a. Try it in the widget above with the second button.

1Console.WriteLine(MinCoins(6, new[] { 1, 3, 4 }));    // 3 + 32Console.WriteLine(MinCoins(10, new[] { 1, 3, 4 }));   // 3 + 3 + 43Console.WriteLine(MinCoins(7, new[] { 2, 4 }));       // impossible4 5static int MinCoins(int amount, int[] coins)6{7    var best = new int[amount + 1];8    Array.Fill(best, int.MaxValue);                    // "not possible yet"9    best[0] = 0;10    for (int a = 1; a <= amount; a++)11        foreach (int c in coins)12            if (c <= a && best[a - c] != int.MaxValue)13                best[a] = Math.Min(best[a], best[a - c] + 1);   // c as the last coin14    return best[amount] == int.MaxValue ? -1 : best[amount];15}

2
3
-1

Time O(amount × number of coins), memory O(amount). Compare with trying all combinations of coins, which grows exponentially with the amount.

1Console.WriteLine(BestInspections(new[] { 2, 7, 9, 3, 1 }));2Console.WriteLine(BestInspections(new[] { 5, 1, 1, 5 }));3 4static int BestInspections(int[] value)5{6    int beforePrev = 0, prev = 0;            // best up to i − 2 and up to i − 17    foreach (int v in value)8    {9        int cur = Math.Max(prev, beforePrev + v);   // skip this site, or take it10        beforePrev = prev;11        prev = cur;12    }13    return prev;14}

12
10