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
Start the list

One row of answers

Each answer depends on the one or two before it.

StatusChallengeLevelSave
1.Climbing StairsCount the ways to climb n stairs taking one or two at a time.Easy
2.House RobberTake the most from a row of houses without taking two neighbours.Medium
3.Maximum SubarrayFind the largest sum of a run of consecutive numbers.Medium
4.Jump GameDecide whether you can jump from the first square to the last.Medium
5.Longest Valid ParenthesesFind the longest balanced run in a string of parentheses.Hard

Choices and counts

Try each choice, keep the best, or count the ways.

StatusChallengeLevelSave
6.Coin ChangeMake an amount with as few coins as possible.Medium
7.Longest Increasing SubsequenceFind the longest strictly rising sequence you can pick out of an array.Medium

A grid of answers

Two positions at once, usually one in each string.

StatusChallengeLevelSave
8.Unique PathsCount the paths across a grid moving only right or down.Medium
9.Edit DistanceCount the fewest single-letter edits that turn one word into another.Hard
10.Pattern MatchingMatch text against a pattern with . and * wildcards.Hard