leetExpert

Module 24 · Dynamic Programming

Practice

Practice~2 min

How to practice this module

DP drills reward naming the state first: what does dp[i] mean, and which choices build it? Climbing-stairs and house-robber are 1-D; coin-change and partition-equal are knapsack-shaped; LIS / LCS and edit-distance are sequence DP; house-robber-iii is tree DP. Done when all ten show Solved in the hub.

Problems

DP — work them in order; difficulty ascends.

0/10

solved

  1. 1Climbing StairsEasy1-D linear recurrenceWatch for: dp[i] = dp[i-1] + dp[i-2]; nail the bases for n = 0, 1, 2 and iterate upward
  2. 2House RobberMediumTake / skip 1-DWatch for: dp[i] = max(skip, rob[i] + dp[i-2]); the empty and single-house bases are where people off-by-one
  3. 3Coin ChangeMediumUnbounded knapsack minWatch for: For each amount, minimise over coin choices; seed dp[0] = 0 and use a large sentinel for unreachable amounts
  4. 4Longest Increasing SubsequenceMediumO(n^2) LISWatch for: dp[i] = 1 + max dp[j] over j < i with nums[j] < nums[i]; the answer is the max over all i, not dp[n-1]
  5. 5Unique PathsMediumGrid fill from cornersWatch for: The first row and column are all 1; each cell sums top + left — loop from the top-left corner
  6. 6Longest Common SubsequenceMedium2-D match tableWatch for: Equal characters -> 1 + diagonal; otherwise max of up / left; pad the table with one zero row and column
  7. 7Edit DistanceHard2-D edit tableWatch for: Insert, delete and replace are the three transitions from the neighbouring cells; base rows are the full length, not 0
  8. 8Partition Equal Subset SumMediumSubset-sum boolean DPWatch for: Target = total / 2 (an odd total fails immediately); iterate amounts high-to-low so an item is never reused
  9. 9Word BreakMediumPrefix-reachable booleanWatch for: dp[i] is reachable if some dp[j] holds and s[j:i] is a word; a trie over the dictionary makes the check cheap
  10. 10House Robber IIIMediumTree DP pairsWatch for: Each node returns (rob, skip); a parent that robs needs both children to skip — post-order is the natural order

Cheatsheet

DP — Subproblems + order — define the state before you code the loop.

Smell → pattern

  • Optimal among overlapping subproblemsDP table / memo
  • Count ways under constraintsTransition sum
  • Knapsack / decide take or skip2D then compress
  • Longest increasing / common subsequenceSequence DP
  • Grid paths with obstacles2D fill from corners

Patterns

State then transition

Core

Smell: You can name ‘best/ways ending at i’

Name dp[i] (or dp[i][j]) in words first. Write the recurrence and base cases. Only then pick loop order — code without a named state is guesswork.

deps → state

Memoised recursion

Safe

Smell: Sparse reachable states; natural recursive structure

Top-down: same recurrence, cache results. Great when bottom-up would fill a huge unused table. Still state the complexity of the cache size.

return

Rolling space

Reach

Smell: dp[i] only needs dp[i−1] (or two rows)

Keep one or two rolling rows after the recurrence is correct. Compressing first is how people invent off-by-one bugs.

deps → state

Decision at each step

Careful

Smell: Take / skip, or choose among prior endings

Write the choices explicitly (take item j, end a subsequence at i…). Transitions that ‘feel right’ without listing choices usually miss a case.

deps → state

Complexity targets

  • 1D sequence DP

    Time
    O(n·T)
    Space
    O(n)
    Note
    T = work per state

  • Classic knapsack

    Time
    O(n·W)
    Space
    O(W)
    Note
    After rolling

  • Grid path DP

    Time
    O(m·n)
    Space
    O(n)*
    Note
    *rolling column/row

Traps

  • Wrong iteration order

    Bottom-up must evaluate dependencies before dependents. Reverse a loop and you silently read stale zeroes — tests pass on tiny cases, fail on real ones.

  • Off-by-one base cases

    Empty prefix, zero capacity, and the first cell of a grid are where most DP bugs hide. Write them before the nested loops.

  • State that is not a decision point

    If dp[i] cannot decide between alternatives at i, you are missing a dimension. Adding the choice to the state is cheaper than a wrong recurrence.