DP Overview & State Design

Dynamic programming is recursion that remembers. When a brute-force search keeps asking the same smaller question ("best answer from index i with cap left"), you store each answer once and reuse it. Most DP problems fall into a handful of patterns, and the wording of the problem usually tells you which one.

The idea#

A DP solution is a function of a state: the smallest set of values that fully decides the answer from this point on. You write it in four steps.

1. State: what changes between subproblems (an index, remaining capacity, a pair of indices, a flag).
2. Transitions: the choices at this state (take or skip, move down or right, match or delete).
3. Base cases: where the recursion stops (ran out of items, crossed pointers, hit the target).
4. Answer: which state you call first, and how you combine the choices (min, max, sum, or).

Those four steps pay off only when the problem has two properties: overlapping subproblems (the same state is reached by many paths) and optimal substructure (the best answer from a state only depends on that state, not on how you got there).

Pattern map#

Once you can write a state, the next question is which shape to reach for. Match the clue in the problem to a pattern below; each pattern has its own note.

Two close relatives live elsewhere. Tree DP (return several states from a postorder call, as in House Robber III) is in Tree DP with States. Kadane's "extend or restart" running state is in Kadane & Running-State DP.

Memo, then table, then space#

Whichever pattern you land on, the code goes through the same three stages. Start top-down with @cache: it's the brute-force recursion plus one decorator. Once it's correct, you can turn it into a bottom-up table that fills states in dependency order. Then keep only the rows the recurrence reads. Here are the three shapes for a recurrence that reads the last two states.

top-down:
    f(i):
        if i is a base case: return its value
        return combine(f(i - 1), f(i - 2))
    memoize f on i; answer f(n)

table:
    dp[base cases] = their values
    for i from the first non-base state up to n:
        dp[i] = combine(dp[i - 1], dp[i - 2])
    answer dp[n]

rolling:
    prev2, prev1 = the two base values  # only two cells are read
    repeat up to n:
        prev2, prev1 = prev1, combine(prev1, prev2)
    answer prev1

The memo version is usually enough in an interview. Mention the table and the rolling version as follow-ups. Move to them when recursion depth is a risk (Python's default limit is about 1000 frames).

Designing the state#

The state is where most DP bugs and slow solutions come from. These four checks catch the usual problems.

Everything the answer depends on must be in the cache key#

@cache only sees the function's arguments. Suppose the answer also depends on something outside them, such as a shared used[] list that the recursion flips on and off. The cache then returns answers computed under a different used[]. The result is wrong, or the code only looks memoized and is still exponential.

This trap shows up most in "choose some of these items" problems written as "loop over every unused item". Each one has a clean state once you fix the order; see the hints below.

Shrink the state when a dimension is redundant#

Even a correct key can carry more than it needs. Ask whether the answer from here depends on how you got here. If order doesn't matter for the answer, the history can usually go, and only "what is left" stays in the state. See Min/Max to a Target.

Flip the question when the obvious state is too big#

Sometimes "the fewest moves to do X" has a huge state, or a slow search inside each state. Flip what the DP returns: "with these resources and m moves, how much can you do?" Then find the smallest m that is enough.

Reduce to a pattern you already know#

Many problems are a known pattern in disguise. Before inventing a new recurrence, ask which pattern the choices look like. The pattern map above is the list to check.

Pitfalls#

Most DP bugs are quiet: the code runs but returns a wrong answer or stays slow. Watch for these.

• A cache key that misses part of the state (see above). This is the most common silent bug.
• Memoizing on string slices (track(word1[:-1], word2)). Each key costs $O(n)$ to build and hash; pass indices instead.
• Writing base cases (such as off-the-grid positions) into the memo. It's harmless but wastes memory; return them directly and cache only real states.
• Off-by-one guards such as if rem < -1 where rem < 0 was meant. A negative remainder must be rejected.
• Taking a modulus only at the end. In Python big integers hide the problem, but the intended solution applies % MOD at every step.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Each one tests a state-design move from this note.

• 70. Climbing Stairs
• 474. Ones and Zeroes
• 646. Maximum Length of Pair Chain
• 1024. Video Stitching
• 279. Perfect Squares
• 740. Delete and Earn
• 1049. Last Stone Weight II
• 583. Delete Operation for Two Strings
• 887. Super Egg Drop

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Write the state, transitions, base cases and answer before writing code.
• The cache key must hold everything the answer depends on; nothing global may leak in.
• Start with @cache, then convert to a table and roll it down to the rows you need.
• Match the problem's wording to a pattern from the map, and look for a reduction to a known one.
• If the state feels too big, drop a redundant dimension or flip what the DP returns.