Skip to main content

Book Exercise Lanes

This module's exercise system is book-driven. Use these local chunks for targeted volume after you have already learned the concept from the guide and implemented at least one solution of your own.

How To Use This Page​

  1. Finish the relevant concept page first.
  2. Derive the recurrence on paper and implement the smallest non-trivial instance from memory.
  3. Only then open the matching exercise lane.
  4. Keep a mistake log with tags such as state missed an index, off-by-one base case, wrong fill order, greedy assumed, ascending instead of descending loop, reconstruction bug, or pseudo-poly treated as polynomial.

Lane 1: DP Foundations and Classical Sequence DP​

Use this lane when you need volume on recognizing DP, defining state, and writing correct recurrences for rod-cutting-shaped and sequence problems.

Target outcomes:

  • 6 recurrences written out explicitly, each with state, base cases, fill order, and complexity
  • 4 naive-recursion vs memoization benchmarks (even informal timing is fine)
  • 3 full reconstructions of the optimal object using parent arrays
  • 2 cases where you wrote the cut-and-paste argument in English before coding

Lane 2: Sequence DP -- LIS, Edit Distance, LCS, Knapsack​

Use this lane when your main weakness is turning a two-sequence or 1D-with-capacity problem into a correct 2D table.

Target outcomes:

  • 3 LIS implementations: O(n^2), O(n log n), and one with explicit reconstruction
  • 2 edit-distance implementations: value-only and with full edit script
  • 3 knapsack variants: 0/1 with rolled array, 0/1 with reconstruction, unbounded
  • 1 LCS implementation and 1 partition/subset-sum implementation
  • Written proof that ascending loop direction turns 0/1 into unbounded knapsack

Lane 3: Interval, Tree, and Advanced DP​

Use this lane once you are fluent with sequence DP and need volume on interval, tree, and subset-shaped DP.

Target outcomes:

  • 2 interval-DP implementations with reconstruction (matrix chain, optimal BST or balloon burst)
  • 2 tree-DP implementations (max independent set and tree diameter)
  • 1 bitmask-DP implementation (TSP or subset-sum enumeration)
  • 1 digit-DP implementation (count numbers in [0, N] satisfying a digit property)
  • Written justification for each of when 2^n * n^2 was affordable and when it was not

Lane 4: Greedy vs DP, DAG DP, and Paradigm Selection​

Use this lane after you can write DP recurrences fluently, when the open question is which paradigm to use at all.

Target outcomes:

  • 4 problems where you wrote an exchange-argument proof for a greedy solution
  • 4 problems where a plausible greedy fails and you produced the counterexample
  • 2 DAG-DP implementations (longest path in DAG, counting paths in DAG)
  • 2 paradigm-selection writeups: one problem solved two ways (greedy + DP or DP + DAG reformulation) with a comparison

Self-Curated Problem Set​

Build a custom set with these minimums:

  • 5 sequence-DP problems (LIS, edit distance, LCS, knapsack)
  • 4 grid-DP problems (paths, obstacles, collect-max)
  • 3 interval-DP problems (matrix chain, balloon burst, palindromic partitioning)
  • 3 tree-DP problems (max independent set, diameter, rerooting)
  • 3 bitmask or digit DP problems
  • 3 greedy problems with proofs

Sources: CSES DP problem set, AtCoder Educational DP Contest, USACO Gold DP, LeetCode "hard" DP section.

Completion Checklist​

  • Completed at least three of the four lanes in full
  • Logged at least 15 real mistakes and corrections with tags
  • Implemented at least 6 full-table DPs with reconstruction, not only value
  • Wrote at least 4 exchange-argument proofs for greedy problems
  • Produced at least 3 counterexamples where a plausible greedy failed
  • Solved at least 2 problems two ways (greedy vs DP, or DP vs DAG reformulation) and wrote the comparison