Dynamic Programming Patterns Refresher

What's being tested

This topic tests your ability to identify a problem's state and transition, pick an appropriate Dynamic Programming strategy (top-down vs bottom-up), and implement it with correct time/space bounds. Interviewers probe whether you can reduce recursion to iterative tables, apply memoization safely, and use space optimization or specialized DP patterns for performance-sensitive production code.

Patterns & templates

• Top-down memoization with recursion (`dfs` + `memo`) — map state→result; clear base cases; good for sparse/irregular state-spaces.

• Bottom-up DP table filling — iterate states in dependency order; explicit loops often avoid recursion limits and show complexity easily.

• Space optimization / rolling array — compress O(n*m) table to O(m) when transitions only use previous row; verify overwrite order.

• Knapsack / subset DP — iterate capacities backward for 0/1 knapsack to avoid reuse; forward iteration for unbounded knapsack.

• LIS via patience sorting — transform O(n^2) DP to O(n log n) with binary search (`bisect`) on tails array.

• Tree DP (post-order) — compute child results, merge into parent; watch for combining multiple child states and commutativity.

• Bitmask DP for small N (N ≤ ~20) — represent subsets as bits, iterate submasks efficiently, complexity ~O(N * 2^N).

Common pitfalls

Pitfall: Choosing recursive memoization without handling recursion depth causes stack overflows on large inputs; convert to iterative if necessary.

Pitfall: Incorrect iteration order (e.g., forward in 0/1 knapsack) yields reuse bugs that change problem semantics.

Pitfall: Over-indexing state (too many dimensions) leads to TLE/MLE—always question whether a dimension can be compressed or eliminated.

Practice these

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