Dynamic Programming

What DP Actually Does

Many problems have recursive structure. Fibonacci, shortest paths, counting combinations, optimal selections. The recursive logic is easy to write. But the recursion recomputes the same subproblems thousands or millions of times. A naive call tree for fib(50) makes billions of redundant calls for a problem with only 50 unique answers.

Dynamic programming eliminates this redundancy. Compute each subproblem once, store the result, and look it up when needed again. The exponential recursion collapses to polynomial time because each subproblem is solved exactly once.

Two Conditions That Enable DP

DP requires two properties working together. Overlapping subproblems means the same computation appears multiple times in the recursion. fib(3) appears under both fib(5) and fib(4). Caching fib(3) after the first computation saves all redundant calls.

Optimal substructure means the optimal answer can be built from optimal sub-answers. The minimum coins to make $11 contains the minimum coins to make $6 (after choosing a $5 coin). The shortest path from A to C through B contains the shortest A-to-B path. If a better sub-answer existed, it could be swapped in to improve the whole, contradicting optimality.

Overlapping subproblems alone means caching helps, but without optimal substructure there is no recurrence to exploit. Optimal substructure alone means a recurrence exists, but if subproblems never repeat, there is nothing to cache. That is Divide & Conquer (Merge Sort, Quick Sort). Both together give DP: a recurrence to exploit and redundancy to eliminate.

DP vs Greedy vs Divide & Conquer

Greedy commits to the locally optimal choice and never reconsiders. DP explores all choices at each state and combines the best sub-answers. Divide & Conquer splits the problem into independent subproblems that do not overlap, so there is nothing to cache.

Recognizing DP Problems

What a DP State Must Capture

A DP state must contain enough information that the remaining decision is independent of how the algorithm got there. If two different paths through the problem arrive at the same state, the optimal continuation must be the same for both. That is what makes caching correct: a cached answer can be reused by any path that reaches the same state.

In practice, define a state like dp[i] that represents the answer to a specific subproblem. Write a recurrence relating dp[i] to smaller states. If the recurrence cannot be written because it needs information that the state does not provide, the state is incomplete. Add a dimension.

What varies between subproblems determines the state shape. One position in a sequence gives Linear DP. Two positions (one in each string) gives String DP. A range with start and end gives Interval DP. Grid coordinates give Grid DP. Items and remaining capacity give Knapsack.

Additional constraints add dimensions. Just the index gives a 1D state. Index plus a constraint (remaining capacity, whether the previous item was taken, current mode) gives a 2D or state machine state.

First Walkthrough: Climbing Stairs

Problem: There are n stairs. Each step can climb 1 or 2 stairs. How many distinct ways are there to reach the top?

State: dp[i] = number of ways to reach stair i. This captures exactly what needs to be known (the count of paths to each intermediate stair) which enables building the count for higher stairs.

Recurrence: To reach stair i, the last move was either from stair i-1 (one step) or from stair i-2 (two steps). These are the only options. The total ways to reach stair i equals the ways to reach i-1 plus the ways to reach i-2: dp[i] = dp[i-1] + dp[i-2].

Base Cases: dp[0] = 1 (one way to be at the ground: do nothing). dp[1] = 1 (one way to reach stair 1: take one step). These are small enough to answer directly.

Fill Order: dp[i] needs dp[i-1] and dp[i-2]. Both have smaller indices. Fill left to right: dp[0], dp[1], dp[2], ... dp[n].

Answer: The question asks for ways to reach stair n, so the answer is dp[n].

Every DP problem follows these same five decisions. The sections below explain each one in detail with harder examples.

The Five-Step Framework

Every DP solution requires these five decisions in sequence. Each builds on the previous. When stuck, the issue is usually in the state definition or the recurrence. Revisit those before proceeding.

Define the State

State definition is where most people get stuck. The recurrence, base cases, and fill order all follow from a correct state. Test your state by attempting the recurrence. If you cannot express dp[i] from smaller states, the state is incomplete. Add a dimension.

State Discovery Method

Start with what the problem asks for. "Maximum money" means dp[i] returns a maximum value. "Number of ways" means dp[i] returns a count. "Is it possible" means dp[i] returns true/false.

Make the simplest guess. Often dp[i] = "the answer for the first i elements" or "the answer ending at position i". Try to write a recurrence with this state.

If the recurrence needs information not in the state, add a dimension. This is how to discover that 2D is needed.

Example: House Robber State Discovery

Wrong Attempt 1: dp[i] = "money from robbing house i only". The optimal strategy for houses 0..i requires knowing what happened at house i-1, but this state only knows about house i, so no recurrence can be written.

Wrong Attempt 2: dp[i] = "maximum money robbing houses 0..i, where house i is robbed". This forces including house i, but the optimal for 0..i might skip house i entirely, so this state cannot express the optimal answer.

Correct State: dp[i] = "maximum money robbing from houses 0..i, with no restriction on whether i is robbed". Now at position i, the algorithm can choose to rob i (gaining nums[i] but skipping i-1) or skip i (taking dp[i-1]). The recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]) works.

Choosing 1D vs 2D State

A well-defined state has a complete answer. For House Robber, dp[3] means "maximum money from houses 0 through 3", fully specified. For Knapsack, dp[3] is incomplete: maximum value using which items? With what remaining capacity? When a single index leaves questions unanswered, add dimensions until the state is unambiguous.

Common reasons for 2D: A resource is being consumed, requiring you to track remaining capacity or budget. Two sequences are being compared, requiring a position in each. A constraint depends on the previous choice, like whether you're currently holding a stock. A range rather than a prefix is relevant, requiring both start and end indices.

Common reasons 1D suffices: Position alone determines the subproblem. No resource is consumed. Only one sequence exists. Constraints are encoded in the recurrence, not the state (House Robber encodes "can't rob adjacent" by using dp[i-2] when robbing).

Find the Recurrence

Every DP recurrence follows the same pattern. At the current state, enumerate all possible choices. For each choice, compute the resulting subproblem plus the cost/value of that choice. Take the best (max, min, sum, OR) across all choices.

Deriving the Recurrence

Question 1: What choices exist at the current state? At house i: rob or skip. At amount a: use any valid coin as the last coin. At string position i: match current char or skip.

Question 2: After making each choice, what smaller subproblem remains? Robbing house i leaves dp[i-2] as the remaining subproblem (can't use i-1). Skipping it leaves dp[i-1]. Using a 5-coin at amount 11 leaves dp[6].

Question 3: How do the choices combine? Want maximum? Take max. Want count? Take sum. Want feasibility? Take OR.

House Robber. At house i, the decision is binary: rob it or skip it. Consider each choice separately.

If house i is skipped, nothing is taken from it. The total money is whatever could be optimally obtained from houses 0 through i-1. By the state definition, that is exactly dp[i-1].

If house i is robbed, nums[i] dollars are gained. But adjacent houses cannot both be robbed. That is the constraint. So if house i is robbed, house i-1 was not. The best outcome from houses 0 through i-2 is dp[i-2]. The total becomes dp[i-2] + nums[i].

Which choice is better? It depends on the specific values, so it cannot be decided in advance. The maximum of both options is taken: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Coin Change. The goal is to make amount a using minimum coins. Think backwards: what was the last coin used?

If the last coin was a 1-coin, then before adding it, amount a-1 remained. The minimum coins to make a-1 is dp[a-1]. Adding that 1-coin gives dp[a-1] + 1 total coins.

If the last coin was a 5-coin, amount a-5 remained before. Minimum coins for a-5 is dp[a-5], so the total is dp[a-5] + 1.

Which coin to use last cannot be known in advance because it depends on the amounts. The algorithm tries all valid coins and takes the minimum: dp[a] = min(dp[a-coin] + 1) for each coin where a >= coin.

Longest Increasing Subsequence. The goal is the longest increasing subsequence ending at index i (which must include nums[i]).

To form an increasing subsequence ending at i, extension from some earlier position j where nums[j] < nums[i] is required. Extending from j yields dp[j] + 1: the longest subsequence ending at j, plus the current element.

Which j to extend from? The goal is the longest result, so all valid j values are checked and the maximum is selected. If no valid j exists (nums[i] is smaller than everything before it), a fresh start with just nums[i] gives length 1.

The recurrence is: dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i]. If no such j exists, dp[i] = 1.

Set Base Cases

Base cases are subproblems small enough to solve directly, without applying the recurrence. The recurrence formula references smaller subproblems (dp[i-1], dp[i-2], etc.), but those references eventually hit invalid indices. The base cases fill in those values so the recurrence has something to work with.

Examine the recurrence. If it accesses dp[i-1] and dp[i-2], then when i=0 or i=1, those indices don't exist. dp[0] and dp[1] must be set directly. If the recurrence accesses dp[i-1][j] and dp[i][j-1], the entire first row and first column must be filled in advance.

To determine base case values, translate dp[0] back to the original problem. Climbing Stairs: dp[0] = ways to reach step 0. Answer: 1 (the starting position). Coin Change: dp[0] = minimum coins for amount 0. Answer: 0 (no coins needed). LCS: dp[0][j] or dp[i][0] = LCS when one string is empty. Answer: 0 (nothing to match).

Verification: compute dp[2] manually. Substitute the base case values into the recurrence and confirm the result matches what is expected from the problem. This catches off-by-one errors before they propagate.

Determine Fill Order

When computing dp[x], every value that dp[x] depends on must already be computed. Violating this reads uninitialized garbage or uses wrong values from a previous state.

What Happens With Wrong Fill Order

Consider computing dp[5] when dp[4] and dp[3] haven't been filled yet. The array was initialized to 0 (or some default). dp[5] = max(dp[4], dp[3] + nums[4]) reads 0 for dp[4] and dp[3], producing a wrong answer. The recurrence is correct, but the values it reads are not. The algorithm silently returns garbage.

Determining Fill Order from the Recurrence

Linear DP: dp[i] depends on dp[i-1], dp[i-2], etc. Dependencies point left. Fill left to right.

Grid DP: dp[i][j] depends on dp[i-1][j] (above) and dp[i][j-1] (left). Fill top-to-bottom, left-to-right within each row.

Interval DP: dp[i][j] depends on dp[i][k] and dp[k+1][j] where i ≤ k < j. Both are shorter intervals. Fill by increasing interval length: all length-1 intervals, then length-2, then length-3.

Stock DP with multiple states: When holding[i] and notHolding[i] both depend on day i-1 values, computing one before the other can overwrite needed values. Either use temp variables for yesterday's values, or compute all of today's states before overwriting.

Extract the Answer

Does the state definition directly answer the original question, or does it answer a constrained version that requires further aggregation?

When the Answer Is in One Cell

If dp[n] is defined as "the answer for the entire input", then dp[n] is the final answer. Climbing Stairs: dp[n] = ways to reach step n. That is exactly the question asked. Coin Change: dp[amount] = minimum coins for that amount. Directly answers the question.

When Aggregation Is Needed

LIS (common bug): dp[i] = length of LIS ending at index i. The question asks for the longest in the entire array, but the LIS might end at index 3, index 7, or the last index. The state constrains where the subsequence ends. The answer requires max(dp[0], dp[1], ..., dp[n-1]).

Returning dp[n-1] is wrong unless the longest subsequence happens to end at the last element. This is a frequent interview bug.

State machine counting: If paths can end in state A or state B, and the question asks for total valid paths, the answer is dp[A] + dp[B]. Each cell counts paths ending in that specific state; summing covers all valid endings.

Top-Down vs Bottom-Up

There are two ways to implement DP: top-down (memoization) and bottom-up (tabulation). Both have the same time complexity, but differ in implementation and practical trade-offs.

Top-Down (Memoization)

Write the recursive solution first, then add a cache. When a function is called, check if the answer is already cached. If yes, return it. If no, compute it, cache it, then return it.

@lru_cache handles memoization automatically. Avoid memo={} as a default argument. Mutable defaults persist across calls in Python, which is a subtle bug.

Pros: Mirrors the recurrence directly (just add caching to recursion), only computes needed states. Cons: Recursion overhead, possible stack overflow for deep recursion.

Bottom-Up (Tabulation)

Build a table iteratively, starting from base cases and filling in the order of dependencies. No recursion needed.

Pros: No recursion overhead, easier to optimize space, often faster in practice. Cons: Must compute all states (even unused ones), order must be carefully determined.

When to Use Which

Neither approach is universally better. The choice depends on the problem structure.

Use memoization (top-down) when only a sparse subset of states is reachable. Many game-theory and constraint problems have huge state spaces where most entries are never touched. Tabulation (bottom-up) is the better choice when most states will be visited anyway, and you want to avoid recursion depth limits or need to optimize space with a rolling array.

DP Families by State Shape

After confirming DP applies, classify the problem by its state shape. DP problems cluster into families with similar state definitions, recurrences, and fill orders. Learning these patterns provides a structured starting point for new problems. Recognizing "this looks like Grid DP" immediately reveals that the state is dp[i][j], the recurrence combines the cell above and to the left, and the fill order is top-to-bottom, left-to-right.

The patterns below cover the vast majority of interview DP problems. For each family, note the state shape, recurrence structure, and fill order.

Linear DP

Linear DP is the simplest and most common DP pattern. The algorithm traverses an array once, left to right, and at each position makes a decision that only requires information from a constant number of previous positions. The "linear" name comes from this single pass through the data.

At position i, the optimal choice depends only on positions already computed. In House Robber, the decision at house i is binary: take house i plus the best achievable through house i-2 (can't rob adjacent houses), or skip house i and keep the best through house i-1. Only two values are needed to make this decision.

Common Variations

Most Linear DP problems fall into one of these dependency patterns. Climbing Stairs and Fibonacci use dp[i-1] and dp[i-2]. House Robber uses the same structure but with a max() choice. Maximum Subarray (Kadane's algorithm) only needs dp[i-1]. Longest Increasing Subsequence needs all of dp[0..i-1] because finding the best previous element smaller than the current one is required.

When Linear DP Breaks Down

If solving position i requires information from positions not yet computed (future positions), a different fill order or a different approach is needed. Decode Ways looks linear at first, but once you realize dp[i] depends on both dp[i-1] and dp[i-2] with different conditions (single digit vs two-digit number), the recurrence is still lookback-2 and works fine. The real break happens when dependencies are unbounded or bidirectional. If the dependency pattern isn't "look backward a fixed distance," 2D DP or a different algorithm may be required.

Grid DP

Grid DP works because movement is constrained. When only right or down moves are allowed, every cell has exactly two predecessors: the cell above and the cell to the left. This constraint makes dependencies predictable and guarantees no cycles.

The core pattern is almost always the same: dp[i][j] combines information from dp[i-1][j] (came from above) and dp[i][j-1] (came from left), then incorporates the current cell's value. For counting paths, they are added. For minimum cost, the min is taken and the current cost added. For maximum path, the max is taken.

Fill Order

The fill order is always top-left to bottom-right because that's the direction of movement. When cell (i, j) is reached, cells (i-1, j) and (i, j-1) are already computed. The first row and first column are often base cases since they have only one predecessor each.

When Grid DP Breaks Down

If movement in all four directions is allowed, cycles exist and DP won't work directly. Use BFS or DFS with memoization instead (or recognize it's a shortest path problem). If obstacles exist, Grid DP still applies but blocked cells are set to 0 or infinity depending on the problem.

Dungeon Game reverses the fill direction. The knight needs at least 1 HP at every cell, and the ending cell's health requirement propagates backward. dp[i][j] = minimum health needed to reach the princess from cell (i, j). Fill from bottom-right to top-left: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Top-left fill fails because the minimum starting health depends on the worst cell along the entire path, which is unknown until the end is reached.

String DP

String DP problems compare two strings by comparing all possible prefixes. The state dp[i][j] represents the answer for the first i characters of s1 and the first j characters of s2. The table is filled cell by cell, where each cell answers: "What's the result given only s1[0..i-1] and s2[0..j-1]?"

Why 1-Indexed Tables

1-indexed tables are used so dp[0][j] and dp[i][0] represent empty prefixes. An empty prefix gives clean base cases: the LCS of any string with an empty string is 0, the edit distance from a string to an empty string is the string's length. Without this, special handling for the first character would be required.

The Decision at Each Cell

At cell (i, j), s1[i-1] is compared with s2[j-1] (the i-th and j-th characters, but 0-indexed in the actual string). If they match, whatever was at (i-1, j-1) can be extended by including this matching character. If they don't match, the best result from either excluding the last character of s1 (dp[i-1][j]) or excluding the last character of s2 (dp[i][j-1]) is taken.

The Off-By-One Trap

The most common bug is using s1[i] instead of s1[i-1]. The table is 1-indexed (dp has size (m+1) x (n+1)) but the strings are 0-indexed. When filling cell (i, j), the question is about the i-th character of s1, which is s1[i-1]. This indexing mismatch is a frequent source of bugs. Tracing through a small example on paper before coding is recommended.

Interval DP

Interval DP applies when the problem requires processing a contiguous segment, and processing that segment involves choosing where to split it. The subproblems are smaller segments within the original.

Why Intervals Need Two Indices

In interval problems, the subproblem isn't "what's the answer up to position i." It's "what's the answer for the segment from i to j." Both endpoints are needed because shrinking from either end gives a different subproblem. dp[2][5] and dp[2][4] are different subproblems, as are dp[2][5] and dp[3][5].

Core Pattern

To solve for range [i, j], the question is: where should this segment be split? Every split point k between i and j-1 is tried. Each split gives two smaller segments [i, k] and [k+1, j]. Those are already solved, so their answers are combined (plus any cost for making that particular split). The best result across all split points is taken.

Why Fill by Interval Length

Filling row by row or column by column fails because dp[i][j] depends on dp[i][k] and dp[k+1][j], which span non-adjacent cells. But both subarrays are shorter than [i, j]. Fill all length-1 intervals first, then length-2, then length-3, and so on. This guarantees every dependency is computed before it's needed.

Burst Balloons: The Backward Thinking Insight

Why forward thinking fails: If balloon k is burst first in range [i,j], its neighbors i-1 and k+1 become adjacent. Now the subproblems [i, k-1] and [k+1, j] interact. The coins from bursting in one range depend on what remains in the other. The subproblems are not independent.

The insight: think about which balloon is burst last. If balloon k is the last one burst in range [i, j], then at that moment:

• All balloons in [i, k-1] are already gone
• All balloons in [k+1, j] are already gone
• Balloon k's neighbors are now nums[i-1] and nums[j+1] (the boundaries of the original range)

The coins from bursting k last = nums[i-1] x nums[k] x nums[j+1]. The left and right subproblems are now independent because the order within each subrange doesn't affect what neighbors k sees when it's burst last.

Stone Game variants use the same interval structure but with min-max game theory. dp[i][j] = best score difference for the current player on range [i,j]. The recurrence alternates: current player maximizes, opponent minimizes.

State Machine DP

Try dp[i] = max profit through day i. The recurrence can't be written. Day i's optimal action depends on whether a stock is held, which isn't captured by a single value. That missing information needs its own dimension. The state becomes dp[i][mode], where mode tracks which actions are legal.

State Machine DP applies whenever the decision at each step depends on what "mode" is active. If the valid actions depend on what happened before (not just the current position), that context must be tracked as a state dimension.

How to Identify States

Ask: "What constrains my choices at this position?" For Stock with Cooldown, holding a stock vs not holding changes the legal actions. Not holding splits further: "just sold" forces a wait, "ready to buy" doesn't. That gives three states: CAN_BUY, HOLDING, COOLDOWN.

Each constraint becomes a state dimension. Stock holding (2 states: yes/no). Cooldown remaining (splits "not holding" into 2). Transactions used for Best Time III/IV (0 to k). The state space is the cross-product of all constraints.

State Transitions

For Stock with Cooldown, the states and transitions form this pattern:

Top-Down: Memoized Recursion

Bottom-Up: O(1) Space

Stock Problem Variants

Beyond stocks: House Robber is a 2-state machine (rob/skip). Paint House is a 3-state machine (one per color, can't repeat). Regex matching maps directly to a finite automaton. The pattern applies whenever legal choices depend on a categorical decision made earlier.

Tree DP

Tree DP works because trees have no cycles: every node has exactly one parent, so the optimal solution at a node can be computed from the optimal solutions of its subtrees. Children are processed before parents (postorder traversal).

Return a Tuple, Not a Single Value

Unlike array DP where dp[i] stores one answer, Tree DP functions return multiple values because the parent's decision depends on which option the child took.

If dfs(child) returns just "best value for this subtree", the parent doesn't know whether that value includes the child node or not. But if the parent wants to include itself, it can't also include its children (adjacent nodes). The parent needs both options from each child: "best if child is included" and "best if child is excluded."

Return a tuple (include_this_node, exclude_this_node). The parent can choose: if including itself, use exclude values from children. If excluding itself, use whichever is better from each child.

House Robber III: Tuple Pattern in Action

The constraint is that two adjacent nodes (connected by an edge) cannot both be robbed. If a node is robbed, its children cannot be. If a node is skipped, its children are free to be robbed or skipped. For each node, two values are computed: rob_this (this node's value plus the skip values of both children) and skip_this (the max of rob or skip from each child).

Why No Memoization?

In grid or string DP, the same cell dp[i][j] can be needed by multiple later cells, creating overlapping subproblems. In a tree, each node has exactly one parent. Every subtree result is computed once and consumed once. No subproblem is ever recomputed.

Reaching for a memo dict in tree DP usually means the structure is actually a graph with cycles, not a tree. If nodes can be reached through multiple paths, the problem requires graph DP with visited tracking, not tree DP.

The Knapsack Family

Knapsack problems are everywhere in interviews, often in disguise. The core structure: items with weights and values, a capacity constraint, and an objective to optimize. Coin Change is knapsack (coins are items, amount is capacity). Partition Equal Subset Sum is knapsack (numbers are items, half the sum is capacity). Target Sum is knapsack with a twist.

The critical distinction is whether each item can be used once (0/1 Knapsack) or unlimited times (Unbounded Knapsack). This single difference changes the recurrence and the loop direction in space-optimized solutions. Getting it wrong means solving a completely different problem.

0/1 Knapsack

In 0/1 Knapsack, each item can be taken at most once, and the goal is to maximize total value without exceeding capacity. The "0/1" name comes from the binary choice: for each item, either take it (1) or leave it (0).

The Decision at Each Cell

dp[i][w] asks: "Using only the first i items and a knapsack of capacity w, what's the maximum value achievable?" For each item, there are two choices. Don't take it: the answer is dp[i-1][w] (best achievable without this item). Take it: the answer is the item's value plus dp[i-1][w - weight] (best achievable with the remaining capacity, using previous items only). Whichever is better is taken.

Why dp[i-1] and Not dp[i]

When taking an item, the lookup is dp[i-1][w - weight], not dp[i][w - weight]. This is critical. Looking at the previous row ensures each item can only be used once. Looking at the current row would allow taking the same item multiple times (that's Unbounded Knapsack). This distinction matters for space optimization: in 0/1 Knapsack, capacity is iterated backwards to avoid reusing items.

Unbounded Knapsack

Unbounded Knapsack allows using each item unlimited times. Coin Change is the classic example: each coin denomination can be used as many times as needed. The question becomes "what's the minimum number of coins to make this amount?"

Why the Loop Order Differs

In Coin Change, when computing dp[amount], the lookup is dp[amount - coin]. Unlike 0/1 Knapsack, using the same row IS desired because reusing coins is allowed. If dp[5] was computed using a coin of value 2, and now dp[7] is being computed, using dp[5] means "take another coin of value 2," which is exactly correct.

This is why space-optimized Unbounded Knapsack iterates capacity forwards while 0/1 Knapsack iterates backwards. Forward iteration allows reusing items. Backward iteration prevents reuse.

Recognizing Unbounded vs 0/1

The key question: "Can this item/coin/choice be used more than once?" If yes, it's unbounded. Coin Change, Climbing Stairs (1 or 2 steps can be taken any number of times), and Cutting Rod are unbounded. Subset Sum, Partition Equal Subset, and the classic Knapsack are 0/1. Getting this distinction wrong means the solution either misses valid answers or counts invalid ones.

Space Optimization

This is an essential interview skill, not optional. After presenting a working DP solution, interviewers frequently ask: "Can we reduce the space?" Having this answer ready demonstrates depth. The pattern is predictable: examine what the recurrence actually uses, keep only that.

Why Space Can Be Reduced

Most DP recurrences only look back a fixed distance. House Robber uses dp[i-1] and dp[i-2], just two values, not the entire history. Knapsack row i only uses row i-1. LCS at dp[i][j] only uses the previous row and current row. The full table stores nxm values but only a fraction are ever accessed simultaneously.

Three Levels of Optimization

2D to 1D: If the 2D table only references the previous row, keep one row and overwrite. Works for Knapsack, LCS, Edit Distance.

1D to constant: If the 1D array only references the previous 1-2 values, use variables instead. Works for Fibonacci, House Robber, Climbing Stairs.

Full grid to single row: Process along the longer dimension, store along the shorter. For a 1000x10 grid, store 10 values, iterate 1000 times.

2D to 1D Reduction

If dp[i][w] only depends on dp[i-1][...], only the previous row needs to be kept. For 0/1 Knapsack, there is a critical twist: iteration must go backwards.

Path Reconstruction

Often the requirement is not just the optimal value, but the actual solution that achieves it. This requires storing decisions, not just values.

How to backtrack: Start at the answer cell and work backwards. At each cell, ask: "Did including this element improve the value?"

Concrete example with LCS: For strings "ABCD" and "AEBD", the answer is at dp[4][4]=3. Check dp[3][3]=2. Different values mean 'D' matched. Record it, move diagonal to [3][3]. At dp[3][3]=2, check dp[2][3]=2. Same value means 'C' did not match. Move to the larger neighbor (left or up). Continue until row 0 or column 0 is reached. Reverse what was collected: "ABD".

The same logic works for Knapsack (which items?), Edit Distance (which operations?), or any DP where the path is needed, not just the number.

Complete Worked Example

Solving Longest Increasing Subsequence from scratch, covering state definition, recurrence, base case, and optimization.

Worked Example: Longest Increasing Subsequence

Given nums = [10, 9, 2, 5, 3, 7, 101, 18], find the length of the longest strictly increasing subsequence.

Step 1: Recognize This Is DP

The word "longest" signals optimization. The goal isn't finding any subsequence, but the best one. There are many increasing subsequences that must be compared. That's the first hint.

Next, check for overlapping subproblems. When computing the LIS ending at index 5, the LIS ending at each earlier index is needed to see which ones can be extended. When later computing the LIS ending at index 6, those same earlier values are needed again. The subproblem "LIS ending at index 3" gets reused when computing results for indices 4, 5, 6, and beyond.

That's both criteria met: optimal substructure with overlapping subproblems. This is DP.

Step 2: Define the State

First attempt: dp[i] = length of LIS in nums[0..i]

Problem: If dp[4] = 2, what that subsequence ends with is unknown. Does it end with 3? With 5? The ending element is needed to decide if extending with nums[5] = 7 is possible.

Better: dp[i] = length of LIS that ends exactly at index i

Now the last element is known to be nums[i]. The check becomes: is nums[i] > nums[j] for some earlier j? If so, extension is possible.

Step 3: Write the Recurrence

dp[i] = the longest increasing subsequence ending at i

For each previous index j where nums[j] < nums[i], the LIS ending at j could be extended by appending nums[i]. The goal is the longest such extension:

If no valid j exists (nums[i] is smaller than everything before it), dp[i] = 1: the element alone forms an increasing subsequence of length 1.

Step 4: Identify Base Cases

Every element by itself is an increasing subsequence of length 1. Initialize dp[i] = 1 for all i.

Step 5: Determine Fill Order

dp[i] depends on dp[j] for j < i. Fill left to right.

Step 6: Identify the Answer

The LIS doesn't have to end at the last index. It could end anywhere. So the answer is max(dp[i]) over all i.

Visualizing the Algorithm

This animation walks through every comparison. For each position i, the algorithm checks all previous positions j to find the longest increasing subsequence it can extend.

The Code

• Time: O(n²): for each of n positions, we check up to n previous positions.
• Space: O(n): single dp array.

When DP Breaks

DP is not always the right approach. Recognizing when it does not apply saves time and avoids forcing a recurrence where none exists.

When greedy works. If the locally optimal choice is provably globally optimal, DP is unnecessary overhead. Activity Selection sorted by end time, Jump Game tracking maximum reachability, and Fractional Knapsack all have greedy proofs. The test: can a small counterexample be found where the greedy choice fails? If not, greedy is likely correct.

When the state space is too large. If describing a subproblem requires tracking too many dimensions (which items are used as a bitmask, exact board configuration, full sequence of moves), the table has exponentially many entries. DP with 2^n states is technically correct but practically no better than brute force. Look for ways to reduce the state: can some dimensions be dropped? Can the problem be decomposed?

When no recurrence exists. If the optimal choice at position i depends on future positions that have not been processed yet, a left-to-right recurrence cannot be written. Dungeon Game looks like it should fill top-left to bottom-right, but the minimum starting health depends on the worst cell along the entire path, which is unknown until the end is reached. The fix is reversing the fill direction, not abandoning DP.

When subproblems do not overlap. If the recursion tree has no repeated nodes, each subproblem is solved exactly once. Caching adds memory without saving time. This is Divide & Conquer. Merge Sort and Quick Sort split the array into independent halves that never appear as subproblems of each other.

Debugging DP

When a DP solution gives wrong answers, work through these questions in order. Most bugs fall into one of these categories.

DP Time and Space Complexity

Time = (Number of unique states) x (Work per state)

Count the distinct inputs to the dp function to get the state count. Examine the recurrence to determine work per state: O(1) for constant-time comparisons (House Robber), O(n) when all previous positions are checked (LIS), O(n) when all split points are tried (Interval DP).

Space equals the state count before optimization. After optimization, it depends on how far back the recurrence looks: lookback-2 gives O(1), previous-row gives O(n), full table stays at O(n x m).

Practice Problems

Organized by pattern and difficulty. Each insight explains the reasoning, not just the formula.

Linear DP

String DP

Knapsack Family

Grid DP

Tree DP

State Machine DP

Reference Templates

Compact code shapes for each DP family. Use these for quick recovery, not first learning.

Linear DP

Use when each position depends on a fixed number of earlier positions.

Grid DP

Use when movement constraints make each cell depend on already-computed neighbors.

String DP

Use when comparing prefixes of two strings with a 1-indexed table.

Interval DP

Use when the subproblem is a range and every split point must be tested.

State Machine DP

Use when legal actions depend on the current mode.

Tree DP

Use when each node needs results from its children before returning to the parent.

0/1 Knapsack (1D)

Use when each item can be used at most once. Iterate capacity backward.

Unbounded Knapsack (1D)

Use when each item can be reused unlimited times. Iterate capacity forward.

Pattern Recap

Linear DP processes a sequence left to right. Each position depends on a fixed number of earlier positions (lookback-1 for Kadane, lookback-2 for House Robber, lookback-all for LIS). The lookback distance determines space optimization.

Grid DP fills a 2D table top-left to bottom-right because movement is constrained to right and down. Each cell combines the cell above and the cell to the left. First row and first column are base cases.

String DP compares all prefix pairs of two strings in a 1-indexed table. When characters match, the diagonal extends. When they do not match, the better neighbor is taken. The off-by-one between 1-indexed table and 0-indexed strings is the most common bug.

Interval DP solves ranges by trying every split point. Fill by increasing interval length so shorter sub-intervals are ready when needed. When choosing what to process first creates coupled subproblems, ask what to process last instead.

State Machine DP adds a mode dimension when legal actions depend on previous choices. Draw the state machine, label transitions, and the recurrence follows from the diagram.

Tree DP returns a tuple from each subtree because the parent's decision depends on which option the child took. Postorder traversal ensures children are solved before parents. No memoization is needed because each subtree is consumed exactly once.

0/1 Knapsack iterates capacity backwards in the 1D optimization to prevent using the same item twice. Unbounded Knapsack iterates forwards because reusing items is allowed.

Rebuilding the Pattern

When a DP problem feels unclear, start with the question the problem asks. "Find the minimum cost" means the state should store a cost. "Count the ways" means the state should store a count. "Is it possible" means the state should store a boolean. The type of answer determines the type of state.

Next, determine what changes between subproblems. A single position changing gives 1D. Two positions (one in each string) give 2D. A resource being consumed (capacity, budget, transaction count) adds another dimension. If deciding what the current step's choices are requires knowing a mode (holding a stock vs not holding), that mode becomes a state dimension too.

Try writing the recurrence with the state you have. If it needs information that the state does not provide, the state is incomplete. Add the missing information as a dimension. If the recurrence can be written, set base cases by translating dp[0] (or dp[0][0]) back to the original problem in plain language. "Ways to reach step 0" is 1. "Min coins for amount 0" is 0. "LCS with an empty string" is 0.

Verify the fill order by checking that every value the recurrence reads is already computed. Then check where the answer lives. If the state fixes something (ending position, current mode), the answer may require scanning all states or summing across modes, not just reading dp[n].

The pattern is recoverable from these decisions: what the state stores, what varies between subproblems, what choices exist at each state, how choices combine, what the base cases mean, what order to fill, and where the answer ends up.

Check Your Understanding

Use these questions to check whether you can reason through the pattern without looking at the template.