8 patterns · 40 problems
Dynamic Programming
Cache overlapping subproblems and build optimal answers from optimal sub-answers.
Each pattern below starts with when to reach for it and the clue in the prompt that gives it away. Then it runs on real problems: pick one to watch the technique step by step, open its full solution, or practise it on an original problem with graded tests.
01Pattern
Basic Dynamic Programming
Solve each subproblem once, reuse the answer.
O(n)naïve O(2^n)When to reach for it
- You encounter a problem where recursive calls result in redundant computations, leading to inefficiency. The problem can be optimized by storing the results of previous computations in a data structure.
Spot it in the prompt
Look for recursive problems where subproblems are overlapping or repetitive.
Climbing Stairs
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.
Rung Ladder Climbs is our own problem on the same technique: a new statement, graded in your browser.
02Pattern
Optimal Substructure
Combine optimal sub-answers into the optimum.
When to reach for it
- You encounter a problem where an optimal solution can be constructed from optimal solutions of its subproblems.
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.
Maximum Subarray
How to solve it
Animation shows the Optimal Substructure techniqueKadane's algorithm extends or restarts the running sum at each index and tracks the best sum seen so far.
Best Trading Day Run is our own problem on the same technique: a new statement, graded in your browser.
03Pattern
Interval/Range DP
Solve small ranges, expand to larger ones.
O(n^3)When to reach for it
- You encounter a problem where you need to find optimal solutions for subintervals within a larger interval.
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.
Minimum Falling Path Sum
How to solve it
Animation shows the Interval/Range DP techniqueFor each cell add the minimum of the three cells above it, then return the smallest value in the last row.
Least Strain Down the Wall is our own problem on the same technique: a new statement, graded in your browser.
04Pattern
Knapsack Problems
Pick items to optimize value under capacity.
O(n * W)When to reach for it
- You encounter a problem where you need to optimize the allocation of resources to maximize or minimize a value, subject to capacity constraints.
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.
Last Stone Weight II
How to solve it
Animation shows the 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.
Trimming The Bar Rack Down is our own problem on the same technique: a new statement, graded in your browser.
05Pattern
Prefix Sums
Precompute cumulative sums for O(1) ranges.
O(n)naïve O(n^2)When to reach for it
- You encounter a problem where you need to efficiently compute cumulative sums or counts over a range of elements.
Spot it in the prompt
Look for problems where you can preprocess the array to compute prefix sums or counts, enabling fast query operations.
Subarray Sum Equals K
How to solve it
Animation shows the Prefix Sums techniqueTrack running prefix sums in a hash map and count how often the sum minus K has appeared before.
Trail Elevation Stretches is our own problem on the same technique: a new statement, graded in your browser.
06Pattern
Counting Problems
Count ways by summing state transitions.
When to reach for it
- You encounter a problem where you need to count the number of ways to achieve a certain outcome, subject to certain constraints.
Spot it in the prompt
Look for problems where you can define states representing counts, and transitions between states correspond to valid outcomes.
Unique Paths III
How to solve it
Animation shows the Counting Problems techniqueBacktrack over the grid counting paths that visit every empty cell exactly once before reaching the end.
Sweeping Every Open Bay Once is our own problem on the same technique: a new statement, graded in your browser.
07Pattern
Interval Partitioning
Sort by endpoint, then partition greedily.
When to reach for it
- You encounter a problem where you need to divide a set of intervals into the minimum number of non-overlapping subsets.
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.
Non-overlapping Intervals
How to solve it
Animation shows the Interval Partitioning techniqueSort by end time and greedily keep each interval that starts after the last kept end, removing the rest.
Drop the Clashing Kiln Runs is our own problem on the same technique: a new statement, graded in your browser.
08Pattern
Probability & Expectations
Propagate probabilities across DP states.
When to reach for it
- You encounter a problem where you need to compute the probability of certain events or the expected value of a random variable.
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.
Knight Probability in Chessboard
How to solve it
Animation shows the Probability & Expectations techniqueDP over remaining moves and cell, spreading each cell's probability equally across its eight knight jumps.
The Piece That Stays on the Grid is our own problem on the same technique: a new statement, graded in your browser.
After the pattern
Now solve one you haven't seen.
Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.
1,194 problems · 15,062 graded tests · free