DSA Factory
Curriculum
Level 4 · Advanced

Dynamic programming

About 48 steps, from the first idea to a mastery test.

  1. Stage 0Remember answersFree
    1. 1Climbing stairs11 min
    2. 2Tiling a 2×n board10 min
    3. 3Minimum cost to climb10 min
    4. 4One, two or three steps at a time10 min
  2. Stage 1One-row DPFree
    1. 1House robber11 min
    2. 2Maximum subarray sum10 min
    3. 3Decode ways12 min
    4. 4Delete and earn12 min
  3. Stage 2Choices per itemFree
    1. 1Can some subset reach this sum?13 min
    2. 2Split into two equal halves10 min
    3. 3Ways to reach a target with plus and minus14 min
    4. 4Best sum without going over11 min
  4. Stage 3GridsFree
    1. 1How many ways to the corner?12 min
    2. 2The cheapest way to the corner11 min
    3. 3Blocked cells count for nothing11 min
    4. 4A grid that isn't rectangular12 min
  5. Stage 4Two stringsFree
    1. 1The longest thread through both strings13 min
    2. 2Three ways to fix a mismatch13 min
    3. 3A run that must stay unbroken11 min
    4. 4Counting every way, not finding one13 min
  6. Stage 5KnapsackFree
    1. 1Every item, once each, best value13 min
    2. 2Unlimited copies, one loop direction flips12 min
    3. 3Fewest pieces, not the most value12 min
    4. 4Counting combinations, not arrangements13 min
  7. Stage 6SubsequencesFree
    1. 1The best chain ending here13 min
    2. 2Counting the best chains, not just their length13 min
    3. 3Weighing the chain, not counting its links12 min
    4. 4Two chains meeting at a peak13 min
  8. Stage 7IntervalsFree
    1. 1Where you split a range matters14 min
    2. 2A helper table, then a smaller decision13 min
    3. 3The split-point idea, on cut positions instead of matrices13 min
    4. 4The last one standing, not the first one gone15 min
  9. Stage 8Counting waysFree
    1. 1A root splits the count in two13 min
    2. 2Every valid last word is its own branch12 min
    3. 3What the newest item's swap does to the rest12 min
    4. 4A second piece needs a second state15 min
  10. Stage 9StatesFree
    1. 1Remember the colour you just used13 min
    2. 2Three situations, one per day14 min
    3. 3Count what you have used15 min
    4. 4Count by state15 min
  11. Stage 10BitmaskFree
    1. 1A set of visited stops fits in one number16 min
    2. 2The number of set bits says whose turn it is15 min
    3. 3Fill one group at a time16 min
    4. 4Keep a pair, and smaller is better16 min
  12. Stage 11MasteryFree
    1. 1Fewest square tiles12 min
    2. 2Longest mirror subsequence14 min
    3. 3Ring of houses12 min
    4. 4Nested boxes15 min
Start freeTry a step first