Pattern10 min read

Dynamic Programming

Recursive subproblems with overlap → memo or tabulate. The hard part isn't the table; it's the recurrence.

dprecursion

Intro

DP is just careful recursion. You define a function f(state) that captures everything that affects the future, write the recurrence in terms of smaller states, and either memoise the recursion (top-down) or fill a table (bottom-up). The trick is finding the right state.

Key insight

Write the brute-force recursion first. If it has overlapping subproblems and an optimal-substructure property, memoising it makes it DP.

Approach

1Identify the decision at each step (take/skip, choose-from-k, …).
2Define dp[state] as the answer to a smaller subproblem of the same shape.
3Write the recurrence: dp[state] = combine(dp[smaller], …).
4Establish base cases.
5Decide top-down (recursion + memo) or bottom-up (loop) based on access pattern.

Complexity

Time

O(states · transitions)

Space

O(states), often reducible to O(transition window)

Code

LC 322 — coin change (bottom-up)python

def coinChange(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]

Pitfalls

Choosing too rich a state — exponential states, blows memory.
Forgetting base cases; recurrence works for n ≥ 1 but not n = 0.
Mixing top-down and bottom-up indexing conventions.

Variants & follow-ups

Longest Increasing Subsequence (LC 300)
Edit Distance (LC 72)
Word Break (LC 139)
Burst Balloons (LC 312)