DP Basics

  • Climbing Stairs → Fibonacci recurrence
  • House Robber → choose/skip recurrence
  • Coin Change → min coins (unbounded knap)
  • LIS → DP + binary search on tails
1 / 3

DP recipe

  1. Define state
  2. Write recurrence
  3. Initialize base cases
  4. Iterate in order
2 / 3

LIS (O(n log n))

  • tails[k] = smallest tail of length k+1
  • Binary search to place each number
  • Length of tails = answer
3 / 3
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.