Cache overlapping subproblems and build optimal answers from optimal sub-answers.
Solve each subproblem once, reuse the answer.
O(n)naïve O(2^n)When to reach for it
Spot it in the prompt
Look for recursive problems where subproblems are overlapping or repetitive.
How to solve it
Ways to reach step n equal the sum of ways to reach n-1 and n-2, so accumulate the running total forward.
Open full solutionCombine optimal sub-answers into the optimum.
When to reach for it
Spot it in the prompt
Look for problems where the optimal solution to the problem can be formed by combining optimal solutions of its subproblems.
How to solve it
Animation: Optimal Substructure techniqueKadane's algorithm extends or restarts the running sum at each index and tracks the best sum seen so far.
Open full solutionSolve small ranges, expand to larger ones.
O(n^3)When to reach for it
Spot it in the prompt
Look for problems where the optimal solution for a given interval can be derived from optimal solutions of its subintervals.
How to solve it
Animation: Interval/Range DP techniqueFor each cell add the minimum of the three cells above it, then return the smallest value in the last row.
Open full solutionPick items to optimize value under capacity.
O(n * W)When to reach for it
Spot it in the prompt
Look for problems where you need to select items from a set to maximize or minimize a value without exceeding capacity constraints.
How to solve it
Animation: Knapsack Problems techniqueSplit the stones into two piles as equal as possible — a 0/1 knapsack toward half the total — and the answer is the leftover difference.
Open full solutionPrecompute cumulative sums for O(1) ranges.
O(n)naïve O(n^2)When to reach for it
Spot it in the prompt
Look for problems where you can preprocess the array to compute prefix sums or counts, enabling fast query operations.
How to solve it
Animation: Prefix Sums techniqueTrack running prefix sums in a hash map and count how often the sum minus K has appeared before.
Open full solutionCount ways by summing state transitions.
When to reach for it
Spot it in the prompt
Look for problems where you can define states representing counts, and transitions between states correspond to valid outcomes.
How to solve it
Animation: Counting Problems techniqueBacktrack over the grid counting paths that visit every empty cell exactly once before reaching the end.
Open full solutionSort by endpoint, then partition greedily.
When to reach for it
Spot it in the prompt
Look for problems where you can sort the intervals by their endpoints and use dynamic programming to find the optimal partitioning.
How to solve it
Animation: Interval Partitioning techniqueSort by end time and greedily keep each interval that starts after the last kept end, removing the rest.
Open full solutionPropagate probabilities across DP states.
When to reach for it
Spot it in the prompt
Look for problems where you can model the problem using probability distributions or expected values and use dynamic programming to compute them efficiently.
How to solve it
Animation: Probability & Expectations techniqueDP over remaining moves and cell, spreading each cell's probability equally across its eight knight jumps.
Open full solutionFDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.
750+ engineers trained · frontend, backend, AWS & AI