Dynamic Programming Patterns For Coding Interviews

What's being tested

Demonstrates ability to convert a problem into a Dynamic Programming state and derive correct transitions, trading time for reuse. Interviewers probe precise state definition, boundary/base cases, complexity reasoning, and when to switch to greedy/graph search. They expect clear memoization/tabulation choices and space/time optimizations.

Patterns & templates

• Top‑down memoization — define recursive dp(state), cache results in a map/array; often easiest to get correctness first.

• Bottom‑up tabulation — build dp[] or dp[][] iteratively; good for guaranteeing O(n)/O(n^2) time and predictable memory.

• Knapsack / subset DP — 0/1 or unbounded variants using dp[w] or dp[i][w]; convert choices into weight/value transitions.

• Sequence DP (LIS/LCS) — use dp[i] or dp[i][j] with clear meaning (best ending at i / best using prefixes i,j); common O(n^2) baseline.

• Bitmask DP — represent subsets as bitmasks for N ≤ ~20, use dp[mask] with O(N*2^N) transitions.

• State compression & rolling arrays — drop a dimension when dp[i] depends only on i-1; convert dp[i][j] to prev[j] to save memory.

Common pitfalls

Pitfall: Defining a state that omits needed context (e.g., forgetting "last taken index") leads to incorrect transitions and overcounting.

Pitfall: Not proving or checking base cases; off‑by‑one in base leads to wrong answers or crashes.

Pitfall: Using naive DP with unnecessary dimensions — causes TLE or MLE when O(n^3) can be reduced to O(n^2) or O(n).

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.