Dynamic Programming (1-D & 2-D)
Define a state over positions, prefixes or pairs of prefixes, build each state from a few smaller ones, and fill the table in dependency order.
Count ways, maximize/minimize, or check feasibility over a sequence, a grid, or two strings: house robber, decode ways, word break, unique paths, edit distance, longest common subsequence.
Time is the number of states times the work per state. Each state is computed once, and most read a constant number of earlier states; a bounded look-back, like word break's scan over word lengths, multiplies the cost by that bound. The table holds one entry per state. When a cell reads only the last one or two cells, or only the row above, you can keep just those and drop the rest.
Dynamic programming (DP) answers a problem by solving a family of smaller versions of it once each and reusing those answers. You need four pieces: a state (exactly what dp[i] or dp[i][j] means), a recurrence (how one state is built from smaller ones), base cases (the empty prefix, row 0 and column 0), and a fill order in which every input is already computed. In the 1-D form the state is a position or a prefix: climbing stairs, house robber, decode ways, word break, maximum subarray and longest increasing subsequence. In the 2-D form it is a grid cell or a pair of prefixes: unique paths, longest common subsequence, edit distance.
Knapsack is DP too, but it has a different shape, and telling them apart is the first move. A knapsack state carries a capacity or target dimension (remaining weight, remaining amount, target sum), each step is a choose-or-skip decision about one item against that budget, and the item order doesn't matter. Here the state is a position in the input itself, order is essential, and each cell looks back a fixed distance (i - 1, i - 2) or at fixed neighbors (up, left, diagonal). A quick test: if you're filling up a number like a sum or a weight, reach for knapsack. If the answer for a prefix, a cell or a pair of prefixes follows from the answers for slightly shorter ones, you're in this pattern.
A reliable workflow is to write the plain recursion first by asking what the last step was, add a memo so each state is solved once, then flip it into a bottom-up loop. The cost is the number of states times the work per state: O(n) for most 1-D problems, O(m * n) for a grid or two strings. Space often shrinks further. When dp[i] reads only dp[i - 1] and dp[i - 2], two variables are enough, and when a row reads only the row above, one or two rows are enough. Keep the full table only when you must rebuild the actual path or alignment, not just its value.
Write down in one sentence what dp[i] (or dp[i][j]) means before writing any code. Once the state is exact, the recurrence falls out of asking what the last step was (last house taken or skipped, last one or two digits, last characters matched or not), and the fill order is whatever computes every input first.
- Leaving the state vague. 'Best up to i' can mean 'using any of the first i elements' (house robber) or 'ending exactly at i' (maximum subarray, longest increasing subsequence), and the recurrence and the final answer differ between the two.
- Seeding the wrong base case. Counting problems need 1 for the empty prefix (decode ways, word break's ok[0] = true, the edge cells in unique paths); a 0 there makes every later cell 0.
- Writing the recursion without a memo. Decode ways and word break branch at every character, so plain recursion is exponential even though there are only n distinct states.
- Off-by-one between a table sized (m + 1) x (n + 1) and 0-indexed strings: dp[i][j] describes text1[:i] and text2[:j], so the characters to compare are text1[i - 1] and text2[j - 1].
- Compressing a 2-D table to one row and overwriting a value a later cell still reads, usually the diagonal dp[i - 1][j - 1] in longest common subsequence and edit distance. Save it in a temporary before you overwrite it.
- Fixed look-back over positions: climbing stairs, house robber, decode ways. dp[i] reads a set number of earlier cells, so a couple of rolling variables replace the array.
- Ending exactly at i, with a running best: maximum subarray (Kadane's algorithm) and longest increasing subsequence, where the answer is the max of dp[i] over all i.
- Prefix with a variable look-back: word break, where ok[i] scans back over every cut j that could end in a dictionary word.
- 2-D grids and string pairs: unique paths and minimum path sum combine the cell above and the cell to the left; longest common subsequence and edit distance combine the diagonal, up and left cells over two prefixes.
// 1-D: dp[i] = answer for the first i elements (define it exactly)
int[] dp = new int[n + 1];
dp[0] = 0; // base case: the empty prefix (1 when counting ways)
for (int i = 1; i <= n; i++) {
// combine a few earlier states, e.g. dp[i - 1] and dp[i - 2]
dp[i] = dp[i - 1];
}
return dp[n];
// 2-D: table[i][j] = answer for a[0..i) and b[0..j), or grid cell (i, j)
int[][] table = new int[m + 1][n + 1];
// base cases: fill row 0 and column 0 (one side empty)
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
table[i][j] = table[i - 1][j - 1]; // use the diagonal
} else {
table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]); // combine up and left
}
}
}
return table[m][n];Problems using this pattern
10Easiest first · Blind 75 above NeetCode 150