State Design Templates

The state-first discipline

The single highest-leverage habit when solving a DP problem: write the state and recurrence on paper before writing any code. The state definition is what determines the algorithm; the code is mechanical translation.

The state has three components: (a) what the parameters are, (b) what the function returns for those parameters, (c) what the base cases are. The recurrence is the rule that defines the function for non-base cases. Skip any of these and you're guessing.

Shape 1, 1D linear

State: f(i) = "the answer for the prefix ending at index i". Transition: a constant or O(i) lookup of earlier f values. The classics live here: Fibonacci, climbing stairs, house robber, longest increasing subsequence.

# Climbing Stairs: f(i) = f(i-1) + f(i-2)
def climb(n):
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(n - 2):
        a, b = b, a + b
    return b

Time: O(n). Space: O(1), only the last two states are needed. The classic 1D rolling-array optimisation.

Shape 2, 2D grid

State: f(i, j) = "the answer for arriving at cell (i, j)". Transition: combine answers from neighbouring cells (typically up and left for standard grid problems). Used for unique-paths, minimum-path-sum, edit distance over a grid layout.

# Unique Paths: f(i, j) = f(i-1, j) + f(i, j-1)
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

Time: O(m × n). Space: O(m × n), reducible to O(min(m, n)) with rolling rows. Standard pattern.

Shape 3, 2D string

State: f(i, j) = "the answer for the first i characters of A and the first j characters of B". Transition: depends on whether A[i] and B[j] match, and what the cheapest neighbouring state is. The shape behind LCS, edit distance, and shortest common supersequence.

# Longest Common Subsequence
def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

Time: O(n × m). Space: O(n × m) → O(min(n, m)) with one row. The "+ 1" indexing is the off-by-one tax for handling the empty prefix; the boundary row and column are zeros.

Shape 4, knapsack

State: f(i, w) = "the best value using items 0..i with capacity w". Transition: for each item, either take it (if it fits) or skip it. The 0/1, unbounded, and bounded variants all share this skeleton.

# 0/1 Knapsack
def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]                          # skip item
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][W]

Time: O(n × W). Space: O(n × W) → O(W). Pseudo-polynomial. W is a number, not a length, so this is exponential in W's bit-width. Knapsack is NP-hard despite the DP.

Shape 5, interval

State: f(l, r) = "the best answer for the subarray a[l..r]". Transition: pick some k in (l, r) as the "last" or "first" choice; combine f(l, k) and f(k, r). Used for matrix-chain multiplication, burst-balloons, palindromic-partition.

The transition iterates over all k, so each state's transition is O(r − l). Across all O(n²) intervals, total work is O(n³).

# Burst Balloons: pick the LAST balloon to burst in [l..r]
def max_coins(nums):
    nums = [1] + nums + [1]                                # boundary sentinels
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):                              # subarray length
        for l in range(n - length):
            r = l + length
            for k in range(l + 1, r):
                dp[l][r] = max(dp[l][r],
                               nums[l] * nums[k] * nums[r] + dp[l][k] + dp[k][r])
    return dp[0][n - 1]

The unusual "pick LAST" reframing matters: when k is the last balloon to burst in [l, r], its neighbours are exactly nums[l] and nums[r] (the sentinels or already-burst boundaries), not the ever-shifting state of remaining balloons.

Shape 6, bitmask DP

State: f(mask) or f(i, mask) where mask is a bitmask over a small set (typically up to 20 elements; 2^20 ≈ 10^6 fits comfortably). Used when the problem requires "which subset have we used so far" and the set is small enough for exponential storage.

# Travelling Salesman Problem (Held-Karp): O(n² × 2^n)
def tsp(dist):
    n = len(dist)
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0                                           # start at node 0
    for mask in range(1 << n):
        for u in range(n):
            if not (mask & (1 << u)) or dp[mask][u] == float('inf'):
                continue
            for v in range(n):
                if mask & (1 << v): continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])
    return min(dp[(1 << n) - 1][u] + dist[u][0] for u in range(1, n))

Held-Karp is the exact DP for TSP. O(n² × 2^n), feasible for n up to about 20. Beyond that, you need approximation algorithms or meta-heuristics; bitmask DP doesn't scale.

Memoisation vs tabulation

Two implementation styles, same algorithm. Memoisation writes the recurrence as a recursive function with a cache decorator (@functools.cache in Python). Tabulation fills an array bottom-up. Pick whichever makes the transitions clearer.

• Memoisation wins when the state space is sparse (only a fraction of states are actually reached), you only pay for what you visit.
• Tabulation wins when the state space is dense and you want to avoid recursion overhead. Also the only option when you need iterative space optimisation (rolling arrays).

For interview problems, write memoised first, it follows the recurrence directly. Convert to tabulation only if the interviewer asks or if the state space is too large for the recursion stack.

State-design checklist

1. What does the answer depend on? The state is the smallest set of parameters that determines the answer at that step.
2. What's the smallest case? The base case, usually the empty input or the single-element input.
3. What's the recurrence? Express the answer for state X in terms of answers for strictly smaller states.
4. Are subproblems shared? If yes, DP is the right tool. If subproblems are all distinct, recursion without memoisation is already optimal, that's divide-and-conquer.
5. What's the running time? States × transitions. Confirm it's polynomial (or pseudo-polynomial for knapsack-style problems).

When DP is the wrong tool

• The problem has only one optimal subproblem decomposition. Divide-and-conquer is enough; no overlap, no caching.
• The state space explodes. If states are exponential and the bitmask trick doesn't apply, DP isn't viable. Reach for approximation, randomisation, or a different algorithmic family.
• A greedy solution works. Some problems that look like DP have an exchange-argument greedy solution that runs in O(n) or O(n log n). Always check.
• The transition isn't "smaller subproblems combine to bigger". Sometimes the structure is "find the best path through a graph", that's shortest paths, not DP (though some shortest-path algorithms are DPs).

Where beginners go wrong

• Writing code before the recurrence. Every off-by-one bug is the shadow of a hazy state definition.
• Confusing "optimal substructure" with "subproblems overlap". Both are required for DP; either alone is insufficient. Optimal substructure means the optimal solution decomposes; overlap means subproblems repeat (so caching helps).
• Optimising space prematurely. Get the full 2D table working first; verify correctness against tests; then roll rows. Premature optimisation gives wrong answers.
• Forgetting that bitmask DP doesn't scale. 2^20 ≈ 10^6 fits; 2^30 ≈ 10^9 does not. The exponential factor is real.

What to read next

The Dynamic Programming module covers each of these shapes with worked examples. The Kadane's Algorithm deep-dive is the simplest 1D DP made explicit. The blog essay Recognise the Shape, Not the Problem applies state-design thinking to interview problems beyond DP.