Dynamic Programming
Practice & Revision
Dynamic Programming pattern recognition decision tree, cheat sheet, and Top 15 must-solve DP interview problems.
1. Introduction
This section serves as your comprehensive reference and practice guide for Dynamic Programming. Master these templates, review the decision tree, and solve the curated Top 15 interview problems to prepare for technical interviews.
2. Dynamic Programming Decision Tree
Use this flow chart to determine the correct DP formulation based on your problem:
3. Revision Cheat Sheet
Common DP Recurrence Formulas
| Pattern | Recurrence Relation | Space Optimization |
|---|---|---|
| Fibonacci / Stairs | dp[i] = dp[i-1] + dp[i-2] | O(1) space using 2 variables |
| House Robber | dp[i] = max(dp[i-1], dp[i-2] + nums[i]) | O(1) space using 2 variables |
| Unique Paths | dp[i][j] = dp[i-1][j] + dp[i][j-1] | O(\min(M, N)) space using 1D row |
| LCS | dp[i][j] = 1 + dp[i-1][j-1] (match) else max(up, left) | O(\min(M, N)) space using 1D row |
| 0/1 Knapsack | dp[w] = max(dp[w], val[i] + dp[w - wt[i]]) | O(W) space (inner loop backwards) |
| Edit Distance | 1 + min(replace, delete, insert) | O(\min(M, N)) space using 1D row |
4. Top 15 Must-Solve DP Problems
5. Problem-Solving Framework
When coding Dynamic Programming solutions, follow this 3-step checklist:
1. Verify both Top-Down & Bottom-Up states:
- In dynamic programming interviews, starting with a Top-Down recursive solution with memoization is extremely clean. It demonstrates your ability to solve the core mathematical relation. Follow this up by rewriting it Bottom-Up using tabulation to prove stack safety and unlock space optimizations.
2. Optimize Tabulation Space:
- If the recurrence transition only references states from the previous step i-1 (or previous row dp[i-1]), you can reduce the space complexity by discarding older rows, keeping auxiliary space at O(1) or O(N) instead of O(N²).
3. Handle Edge Cases Early:
- Ensure you correctly initialize boundary values (e.g. dp[0] for 1D, or row 0 / column 0 for 2D grids). Missed base cases will propagate incorrect results across the entire table.
6. Quiz
Question 1: In 'House Robber III' (Tree DP), why is memoization not required if we return pairs [robThisNode, skipThisNode]?
Answer: Because returning a pair containing both choice options allows us to solve each subtree exactly once during a post-order traversal. Each node is visited only once, completely avoiding overlapping redundant subproblem lookups.Question 2: Why is the time complexity of 'Burst Balloons' O(N^3)?
Answer: Because we solve the problem over all possible intervals. There areO(N²) intervals, and for each interval (i, j), we loop K from i to j (O(N) choices) to choose which balloon to burst last, leading to O(N³) overall operations.
Question 3: When does Top-Down Memoization use more memory than Bottom-Up Tabulation?
Answer: Top-Down Memoization requires extra memory for the recursion call stack, which can reachO(N) depth, whereas Bottom-Up Tabulation runs iteratively inside simple loops.
Question 4: True or False: Any problem with overlapping subproblems can be solved optimally using Greedy algorithms.
Answer: False. Greedy algorithms only work if the problem satisfies the greedy choice property (where a local choice guarantees a global optimum). If local choices restrict future optimal selections, DP must be used instead.Question 5: What is the optimal time complexity of the Longest Increasing Subsequence (LIS) problem?
Answer:O(N log N) time, achieved by combining patient sorting with binary search on a tails array tracking active subproblem boundaries.