Blog
Dynamic programming has the worst reputation of any interview topic, and the reason is how it is taught: as a list of famous problems. Climbing stairs, coin change, longest increasing subsequence, edit distance. Learn them one at a time and every new DP problem looks new.
It is not. The 51 DP problems in DSA Tracker's curated set reduce to six state shapes. If you can name the shape, you can write the transition.
Everything else, memoization versus tabulation, space optimisation, reconstructing the actual answer, is mechanical once those two are right.
State: dp[i] = the answer for the prefix ending at position i.
Transition: dp[i] depends on a constant number of earlier entries, often dp[i-1] and dp[i-2].
Classic problems: climbing stairs, house robber, decode ways, maximum subarray (Kadane's algorithm is exactly this with dp[i] = max(nums[i], dp[i-1] + nums[i])).
This is the pattern to make automatic. Step through climbing stairs in the visualizer and watch how each cell only reads the two before it.
State: dp[i][c] = best answer using the first i items with capacity c remaining.
Transition: either skip item i or take it: dp[i][c] = max(dp[i-1][c], value[i] + dp[i-1][c - weight[i]]).
The 0/1 variant lets each item be used once; the unbounded variant loops capacity upward so the same item can be reused. Classic problems: 0/1 knapsack, subset sum, partition equal subset sum, coin change (number of ways and minimum coins), target sum.
The tell in the statement: "choose a subset such that the total is exactly / at most X". That word total against a limit is knapsack.
State: dp[i][j] = the answer for the first i characters of A and the first j characters of B.
Transition: if A[i] == B[j] extend the diagonal, otherwise take the best of dropping one character from either side.
Classic problems: longest common subsequence, edit distance, shortest common supersequence, distinct subsequences, wildcard and regular expression matching.
These are the DP problems that separate candidates at product companies. Edit distance in particular is asked at Google and Microsoft often enough that it is worth being able to write it cold.
State: dp[r][c] = the answer for reaching cell (r, c).
Transition: from the cell above and the cell to the left (or the three cells behind for diagonal moves).
Classic problems: unique paths, minimum path sum, maximal square, dungeon game (which is the same idea solved backwards from the goal).
Grid DP is the easiest pattern to space-optimise: you only ever need the previous row, so a 2-D table becomes two 1-D rows.
State: dp[l][r] = the answer for the subarray from l to r.
Transition: choose a split point k between l and r, combine dp[l][k] and dp[k+1][r], and add the cost of the split.
Classic problems: matrix chain multiplication, burst balloons, minimum cost to merge stones, palindrome partitioning (minimum cuts).
Interval DP is O(n^3) and you should say that out loud. It is the pattern candidates most often fail to recognise, because the "choose the last thing to happen" trick (burst balloons picks the last balloon to pop, not the first) is counter-intuitive.
State: dp[i] = the length of the best subsequence ending at index i.
Transition: dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]), which is O(n^2); the O(n log n) version replaces the inner scan with a binary search over a tails array.
Classic problems: longest increasing subsequence, Russian doll envelopes, maximum length of pair chain, number of LIS.
This is a linear DP with a non-constant lookback, which is why it gets its own pattern.
Do them in this order, five problems each, and do not move on until the transition for the current pattern comes out without thinking:
Patterns 1 to 3 cover what mass recruiters and most first rounds ask. Patterns 4 to 6 are what you add for product companies. If your target role in DSA Tracker is a data or ML role, DP is weighted lower in your plan than for a backend SDE, and that is correct: spend the time on arrays, strings and SQL instead.
Write the recursion first. A correct exponential solution with a cache on top is a correct DP. Going straight to a table is where the off-by-ones live.
Say the state in words. "dp[i][c] is the best value using items 0 to i with capacity c left." If you cannot say it, the transition will be wrong.
Check the base case against the smallest input. An empty string, a capacity of zero, a single cell. Most wrong answers are a base case that returns 0 where it should return 1, or the other way around.
Memoization first. Write the plain recursion, notice it recomputes the same subproblems, and cache the results. That gets the state right, which is the hard part. Convert to a bottom-up table only when an interviewer asks for it or when recursion depth is a real limit.
Around 25 to 30 well-chosen problems covering all six patterns, solved until you can write each transition from memory. Solving 150 DP problems at random is slower than solving 5 per pattern deliberately.
Linear (1-D) DP and 0/1 knapsack style problems dominate first rounds; string DP such as longest common subsequence and edit distance shows up in later rounds and at product companies. Grid DP is common at companies that like matrix questions.
Most sliding window questions are one of two templates. Once you can tell a fixed window from a variable one in the first ten seconds, the rest is bookkeeping.
48 of the 370 problems in our curated set are graph problems, more than any topic except DP. Four algorithms, learned in the right order, cover almost all of them.
