Dynamic Programming
Solve every subproblem once, then let the table do the work.
Dynamic Programming progress0 / 20
- What Is Dynamic Programming?Solve each overlapping subproblem once, then reuse the answer.5m
- Top-Down vs Bottom-UpOne recurrence, two directions: recurse and cache, or fill a table.5m
- Climbing StairsWays to reach step n = ways to n-1 plus ways to n-2.4m
- House RobberTake this one and skip its neighbour, or skip it and keep the best.5m
- Coin ChangeFewest pieces to hit a target, one amount at a time.6m
- Longest Common SubsequenceMatch the two ends, or drop a character from one side.6m
- 0/1 KnapsackEach item is all or nothing, so try both and keep the better.6m
- Edit DistanceInsert, delete, or replace — count the cheapest route.6m
- Longest Increasing SubsequenceEvery element asks which smaller one it can extend.6m
- DP on GridsEach cell's answer comes from the cells above and to its left.6m
- Unbounded KnapsackSame table, forward loop — and every item can be taken again.6m
- Counting Ways, Not CoinsLoop coins on the outside and each combination is counted once.6m
- Equal SplitCan any subset hit exactly half the total? Track reachable sums.6m
- House Robber in a CircleFirst and last are now neighbours, so run the line twice.5m
- LIS in O(n log n)Keep the smallest possible ending for a chain of each length.7m
- Interval DPAnswer every short stretch first, then split the long ones.7m
- DP on TreesEvery node returns two answers: taken, and not taken.7m
- Word BreakA prefix is splittable if some earlier cut leaves a real word.6m
- Reading the Answer BackThe table holds the score; walking it backwards holds the answer.6m
- DP as a State MachineTwo running totals, one per state, updated day by day.6m
Quiz yourself: 3 questions from this module
1 / 3