Level 4 · Advanced
Free Dynamic programming lessons
12 lessons, about 134 minutes in all. Each teaches one idea with a visual, then gives you one problem built for it. Read the lessons here, then create a free account to solve the problems and keep your progress.
Stage 0Remember answers
- Climbing stairsPlain recursion recomputes the same smaller cases over and over; a cache remembers them instead.11 min
- Tiling a 2×n boardInstead of recursing top-down with a cache, build the answer bottom-up in a plain array.10 min
- Minimum cost to climbSame bottom-up array, but the recurrence takes the smaller of two costs instead of adding two counts.10 min
- One, two or three steps at a timeThe recurrence now looks back three steps instead of two; keep only the last three values, not a whole array.10 min
Stage 1One-row DP
- House robberAt each item, choose to take it (and skip the one before) or leave it — keep whichever choice wins.11 min
- Maximum subarray sumExtending a run only helps if it's still positive overall; otherwise start fresh from here.10 min
- Decode waysEach position can be reached by reading one digit or two, but not every reading is valid — check before counting.12 min
- Delete and earnGroup numbers by value first, and the problem becomes House robber over the value line instead of the array.12 min
Stage 2Choices per item
- Can some subset reach this sum?For every number, either it's in the subset or it isn't — track every sum that's reachable either way.13 min
- Split into two equal halvesSplitting into equal halves is the same reachable-sum question, aimed at exactly half the total.10 min
- Ways to reach a target with plus and minusTurn a plus/minus assignment problem into a subset-sum counting problem with some algebra first.14 min
- Best sum without going overTrack every reachable sum as before, then read off the largest one that doesn't exceed the limit.11 min
There’s more after this
These are the opening stages of Dynamic programming. The full path climbs on to harder problems and a mastery test. Create a free account and we’ll keep your place.
Start the full path free