Skip to main content

🧩 Dynamic Programming

DP is just recursion with memoization, recognized. Identify the state (what defines a unique subproblem) and the recurrence (how subproblem answers combine). Everything else is implementation detail.

This category contains 38 problems. Use the patterns below to recognize what's being asked, then jump to the problem list at the bottom.

🧠 Key Patterns​

  • 1D DP — House Robber, Climbing Stairs, Decode Ways. State = index.
  • 2D DP — LCS, Edit Distance, Interleaving. State = (i, j) on two strings.
  • Knapsack — 0/1 vs Unbounded. Capacity + item index as state.
  • Interval DP — Matrix Chain, Burst Balloons. State = (l, r). Try every split point.
  • Grid DP — Unique Paths, Min Path Sum. State = (i, j) cell.
  • Bitmask DP — TSP, assignment. State = (mask, last). Sets up to ~20 elements.
  • State Machine — Stock problems. State = (day, holding, transactions_left).

⚠️ Common Pitfalls​

  • Starting from tabulation when memoized recursion is clearer. Write recursion first, then add memo.
  • Wrong base case (empty string, zero capacity).
  • Forgetting space optimization: many 2D DPs only need the previous row.

📚 Study Resources​

📺 Videos​

📖 Books​

🌐 Articles & References​

💻 All Dynamic Programming Problems​

Last updated on