Dynamic programming from zero
Dynamic programming is recursion that remembers: write the answer for a big input in terms of smaller ones, then fill a table so each smaller answer is worked out once. Start with one row of answers and finish with a grid.
Challenges
10
Easy
1
Medium
6
Hard
3
One row of answers
Each answer depends on the one or two before it.
| Status | Challenge | Topics | Level | Accepted | Save |
|---|---|---|---|---|---|
| 1.Climbing StairsCount the ways to climb n stairs taking one or two at a time. | Dynamic programmingMathRecursion | Easy | – | ||
| 2.House RobberTake the most from a row of houses without taking two neighbours. | Dynamic programming | Medium | – | ||
| 3.Maximum SubarrayFind the largest sum of a run of consecutive numbers. | ArraysDynamic programmingGreedy | Medium | – | ||
| 4.Jump GameDecide whether you can jump from the first square to the last. | ArraysGreedyDynamic programming | Medium | – | ||
| 5.Longest Valid ParenthesesFind the longest balanced run in a string of parentheses. | StringsStacksDynamic programming | Hard | – |
Choices and counts
Try each choice, keep the best, or count the ways.
| Status | Challenge | Topics | Level | Accepted | Save |
|---|---|---|---|---|---|
| 6.Coin ChangeMake an amount with as few coins as possible. | Dynamic programming | Medium | – | ||
| 7.Longest Increasing SubsequenceFind the longest strictly rising sequence you can pick out of an array. | Dynamic programmingBinary search | Medium | – |
A grid of answers
Two positions at once, usually one in each string.
| Status | Challenge | Topics | Level | Accepted | Save |
|---|---|---|---|---|---|
| 8.Unique PathsCount the paths across a grid moving only right or down. | Dynamic programmingMathMatrices | Medium | – | ||
| 9.Edit DistanceCount the fewest single-letter edits that turn one word into another. | StringsDynamic programming | Hard | – | ||
| 10.Pattern MatchingMatch text against a pattern with . and * wildcards. | StringsDynamic programmingRecursion | Hard | – |