Dynamic Programming: From Recursion to a Table

DP is "remember what you've already computed." That's the whole idea. The hard part is finding the right recursion.

Example: longest increasing subsequence

Given [3, 1, 4, 1, 5, 9, 2, 6], find the length of the longest strictly-increasing subsequence (not contiguous, just in order). Answer: 4 (1, 4, 5, 9 or 1, 4, 5, 6).

Naive recursion

def lis(a, i, prev):
    if i == len(a):
        return 0
    best = lis(a, i + 1, prev)              # skip
    if prev is None or a[i] > prev:
        best = max(best, 1 + lis(a, i + 1, a[i]))   # take
    return best

This is correct and O(2^n). Every recursion branches twice. Exponential is bad.

The repetition

The state of a subproblem is (i, prev). There are at most n × n such states, but the recursion will visit many of them many times. Memoizing kills the duplication:

from functools import lru_cache

def lis(a):
    @lru_cache(maxsize=None)
    def rec(i, prev_idx):
        if i == len(a):
            return 0
        best = rec(i + 1, prev_idx)
        if prev_idx == -1 or a[i] > a[prev_idx]:
            best = max(best, 1 + rec(i + 1, i))
        return best
    return rec(0, -1)

Now we compute each (i, prev_idx) pair at most once → O(n²).

The bottom-up version

dp[i] = length of the longest increasing subsequence ending at index i.

def lis(a):
    dp = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

Same O(n²), but no recursion overhead. It's also clearer once you see it: at position i, you're asking "what's the best run I can extend?"

And one trick more

LIS has an O(n log n) solution that uses patience sorting — maintain piles where each pile's top card is the smallest possible final element of a length-k subsequence. Card lookups are binary searches. Beautiful and worth a separate post.

How to spot a DP

You're looking at a problem where:

1. The optimal solution can be built from optimal solutions to smaller subproblems.
2. The same subproblems show up many times in the recursion tree.

If only (1) holds, you have divide-and-conquer (mergesort, FFT). If both hold, you have DP. Memoize first, write the table second, refine the dimensions third.