Optimization line
1-D Dynamic Programming problems
Problems where the answer at a position depends on answers just before it. Store each answer once in a list, and a search that would take exponential time takes one pass.
- 2 easy
- 10 medium
The 12 problems
In the order the app teaches them. Each page has the problem, five hints and the explained solution.
- Climbing StairsEasy
- Min Cost Climbing StairsEasy
- House RobberMedium
- House Robber IIMedium
- Longest Palindromic SubstringMedium
- Palindromic SubstringsMedium
- Decode WaysMedium
- Coin ChangeMedium
- Maximum Product SubarrayMedium
- Word BreakMedium
- Longest Increasing SubsequenceMedium
- Partition Equal Subset SumMedium
On the roadmap
1-D Dynamic Programming is a station on the optimization line. It builds on Backtracking. Next comes 2-D Dynamic Programming.
The roadmap says why each line runs in its order.
Patterns
3 patterns solve these problems. Naming them gives the problems’ methods away, so the list is folded.
Show the 3
- One-dimensional dynamic programming8 problems
- Expand around a center2 problems
- Knapsack dynamic programming2 problems