Dynamic Programming (DP) solves problems with overlapping subproblems by solving each subproblem once and storing the result. It turns exponential brute-force recursion into polynomial time — at the cost of memory.

When to Reach for DP

A problem is a candidate for DP when it has two properties:

1. Optimal substructure — the optimal solution is built from optimal solutions of subproblems.
2. Overlapping subproblems — the same subproblem is computed repeatedly during recursion.

Classic signal: a naive recursive solution recomputes the same states. The Fibonacci recursion, for example, recomputes fib(n-2) twice, fib(n-3) three times, and so on.

The Two Flavors

• Memoization (top-down): keep the recursive structure, but cache results in a table before returning. Intuitive, but pays the recursion-call overhead.
• Tabulation (bottom-up): fill a table from the base cases upward using the recurrence. Faster, no recursion, but requires you to order states correctly.

Both compute the same table; choose memoization for clarity on complex states and tabulation for raw speed.

Designing the Recurrence

The hardest part of DP is defining the state — the minimal information that determines a subproblem’s answer. Ask three questions:

1. What changes between subproblems? Those are your state dimensions (i, w, j).
2. What decision does the recurrence make? Usually “include or skip”, “take this coin”, or “which character to align”.
3. What are the base cases? The states you can answer without further recursion.

For 0/1 Knapsack: state = (items considered, capacity), decision = take/skip, base = zero items or zero capacity.

A Worked State-Space Walkthrough: Longest Increasing Subsequence

The skill is reading a problem into a state. Take LIS: “longest strictly increasing subsequence of A.” Brute force enumerates all 2ⁿ subsequences — far too many. Here is the walkthrough:

1. Brute force first. Recursively: f(i, last) = longest increasing subsequence using A[i..] with the restriction that the next element must be > last. Two parameters change as we recurse: the position i, and the value last. Those are the state.
2. Simplify the state. last is a value, which makes the state space huge — every possible value. The classic move: fix the subsequence’s end instead. Redefine dp[i] = length of the longest increasing subsequence ending at index i. One parameter, n states.
3. Write the recurrence from the decision. To end at i, the previous element must be some j < i with A[j] < A[i], and then the length is dp[j] + 1. Take the best:

   dp[i] = 1 + max{ dp[j] : j < i and A[j] < A[i] }   (or 1 if none)
   answer = max over all i of dp[i]

4. Check the base case. dp[0] = 1 (a single element is an increasing subsequence of length 1); the formula naturally gives 1 when no predecessor qualifies.
5. Complexity falls out of the state. n states, each scanned over up to n predecessors → O(n²) time, O(n) space. The state-space definition is the complexity analysis.

Choosing the state is the entire difficulty. A poor state (last = value) gives a space too large to tabulate; a good state (end at index i) fits in one array. Every DP problem rewards the same three-question analysis before any code is written.

Common State Patterns

Step-by-Step Recipe

1. Write a brute-force recursive solution first.
2. Identify the state from the changing parameters.
3. Write the recurrence as state → best(next states).
4. Add base cases.
5. Implement top-down (memo) or bottom-up (table).
6. If the problem asks for the solution itself (not just its value), add a reconstruction pass that walks the table backward.

Practice Trajectory

Start with 1D states (Fibonacci, LIS, house robber), move to 2D states (LCS, knapsack, coin change), then intervals (matrix chain), then bitmask DP for small sets. DP is a skill built by volume — each problem teaches a new state shape.