Dynamic Programming

Dynamic programming handles problems with overlapping subproblems — edit distance, resource allocation with constraints, path counting. The classic tell: "have I solved a smaller version of this before?"

What it solves

Problems where a solution is built from optimal solutions to subproblems, and those subproblems recur. If the naive recursion recomputes the same thing over and over, DP replaces that with remembering.

Recognition signals

• "Number of ways to…", "minimum cost to…", "longest common…", "edit distance"
• "With at most k…", "each item used once", constrained allocation
• A recursive structure where the same subproblem is reached many times
• "Have I seen this subproblem before?" — the DP tell
• Grid path counting, sequence alignment, knapsack-style constraints

The approach

Two styles, same idea:

The state is everything. For edit distance, the state is (i, j) = "cost to convert the first i characters of A to the first j characters of B". For path counting on a grid, (r, c) = "number of ways to reach that cell". If you can't state the state in a sentence, you don't understand the problem yet — and neither will the AI.

What to tell the AI

This is the pattern where you must define the state yourself:

Implement edit distance with memoization. State: dp(i, j) = min edits to turn the first i chars of A into the first j chars of B. Base cases: dp(i,0)=i, dp(0,j)=j. Recurrence: if A[i-1]==B[j-1], dp(i,j)=dp(i-1,j-1), else 1+min(dp(i-1,j), dp(i,j-1), dp(i-1,j-1)). Cache results in a 2D array.

What to verify

• Memo key correctness — the cache key must include every state argument. A missing dimension silently returns wrong answers.
• Base cases — wrong base cases corrupt the whole table; check both empty sides.
• Indexing — off-by-one between dp(i,j) and array indices is the AI's most common slip.
• Recurrence matches the problem — the AI may swap a min for max, or drop the skip operation.
• State invented by the AI — if you didn't specify the state and the code "works", you're defending a table you don't own. Reprompt with the state.
• Space — ask whether it can run with only two rows when that's possible (edit distance), and whether it did.

Worked micro-example

Edit distance between CAT and CAR. State (i,j), bases dp(i,0)=i, dp(0,j)=j. Row by row: dp(1,1): C==C → 0. dp(2,2): A==A → 0. dp(3,3): T≠R → 1+min(dp(2,3), dp(3,2), dp(2,2)) = 1+min(2,2,0) = 1. So one substitution: CAT → CAR. The memo table makes the subproblems explicit — which is what you narrate.

Practice problems

Try these: Spell Checker (edit-distance ranked suggestions), Word Container (prefix/word lookup with DP-adjacent memoized searches), Transcribe (transform pipelines with optimal ordering).