Dynamic Programming Interview Guide

What is dynamic programming and when should you use it in interviews?

Dynamic programming is an optimization technique that solves problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the result to avoid redundant computation. Use it when a problem has optimal substructure (optimal solution can be built from optimal solutions to subproblems) and overlapping subproblems (same subproblems are solved repeatedly in a naive recursive approach).

---

Dynamic programming is widely considered the most difficult topic category in coding interviews. Problems that require DP often seem unsolvable without a specific insight, and the variety of DP problem types is large enough that pattern recognition is the primary skill needed. This guide covers how to recognize DP problems, the systematic approach to solving them, and the most common DP patterns tested in interviews at major technology companies.

The Two Conditions for Dynamic Programming

Before attempting a DP solution, verify that both conditions are present.

Optimal substructure — The optimal solution to the problem contains within it optimal solutions to subproblems. For example, the longest common subsequence of two strings contains within it the longest common subsequence of shorter versions of those strings.

Overlapping subproblems — A recursive breakdown of the problem recomputes the same subproblems multiple times. If each subproblem only appears once, divide and conquer (like merge sort) is appropriate rather than DP.

"When I see a candidate immediately reach for dynamic programming on every optimization problem, I know they are pattern-matching without understanding. The first question I always ask is: can they articulate why this problem has optimal substructure? If they cannot, they are applying a template, not solving a problem." — Senior engineer and interview panel lead, major technology company

The Four-Step DP Problem-Solving Framework

Step 1: Define the Subproblem

Express the subproblem as a function of a state variable. The state variable captures the information you need to make decisions at each step.

For Fibonacci: dp[i] = the ith Fibonacci number. For 0/1 Knapsack: dp[i][w] = maximum value achievable using items 1..i with weight limit w. For Longest Common Subsequence: dp[i][j] = length of LCS of the first i characters of string A and first j characters of string B.

Step 2: Define the Recurrence Relation

Write the mathematical relationship between the current state and previous states. This is the core of the DP solution.

For Fibonacci: dp[i] = dp[i-1] + dp[i-2] For LCS: if A[i] == B[j], then dp[i][j] = dp[i-1][j-1] + 1, else dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Step 3: Identify the Base Cases

Define the smallest subproblems that have known answers without further recursion.

For Fibonacci: dp[0] = 0, dp[1] = 1 For LCS: dp[0][j] = 0 for all j, dp[i][0] = 0 for all i

Step 4: Determine the Computation Order and Final Answer

Fill the DP table in an order where every subproblem you need is computed before you need it.

For linear DP (Fibonacci), compute left to right. For 2D DP (LCS, Knapsack), typically compute top to bottom, left to right.

The final answer is usually dp[n] or dp[n][m] for some problem-specific n and m.

Top-Down vs. Bottom-Up DP

There are two implementation approaches for DP problems.

Top-Down (Memoization)

Start with the original recursive solution and add a memo cache to store results of subproblems as you compute them.

Advantages: More natural to think through recursively; only computes subproblems you actually need. Disadvantages: Recursion stack overhead; risk of stack overflow for large inputs.

Bottom-Up (Tabulation)

Fill a DP table iteratively, starting from base cases and building up to the final answer.

Advantages: No recursion overhead; naturally produces iterative code; easier to optimize space. Disadvantages: Requires thinking through the computation order more carefully.

Which to Use in Interviews

Start with top-down if it is easier to formulate the recurrence recursively. If the interviewer asks about space optimization or if the recursion depth is large, switch to bottom-up. Many experienced candidates solve DP problems with top-down memoization by default because it maps more naturally to the recursive intuition.

Core DP Patterns and Problem Examples

1. Linear DP

State: Single variable representing position in a linear sequence. Classic problems: Fibonacci, Climbing Stairs, House Robber, Coin Change.

Coin Change pattern: Given coins of various denominations, find the minimum number of coins to make a target amount.

• State: dp[i] = minimum coins to make amount i
• Recurrence: dp[i] = min(dp[i - coin] + 1) for all coins where coin <= i
• Base case: dp[0] = 0
• Complexity: O(amount * num_coins) time, O(amount) space

2. Two-Sequence DP

State: Two variables representing positions in two sequences simultaneously. Classic problems: Longest Common Subsequence, Edit Distance, Longest Common Substring.

Edit Distance: Minimum operations (insert, delete, replace) to transform string A into string B.

• State: dp[i][j] = edit distance between first i chars of A and first j chars of B
• Recurrence: if A[i-1] == B[j-1], dp[i][j] = dp[i-1][j-1], else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
• Complexity: O(mn) time and space, reducible to O(min(m,n)) space with row optimization

3. Knapsack DP

State: Item index and remaining capacity. Classic problems: 0/1 Knapsack, Partition Equal Subset Sum, Target Sum.

Partition Equal Subset Sum: Can the array be partitioned into two subsets with equal sum?

• Reduce to: can any subset sum to total_sum / 2?
• State: dp[i][s] = whether subset of first i items can achieve sum s
• This reduces to a boolean knapsack problem
• Complexity: O(n * target) time and space

4. Interval DP

State: Interval boundaries [i, j]. Classic problems: Matrix Chain Multiplication, Burst Balloons, Palindrome Partitioning.

Burst Balloons: Maximum coins from bursting all balloons in optimal order.

• Key insight: think about which balloon is burst last, not first
• State: dp[i][j] = maximum coins from bursting all balloons between i and j exclusively
• Complexity: O(n³) time, O(n²) space

5. Path DP (Grid Problems)

State: Grid coordinates. Classic problems: Unique Paths, Minimum Path Sum, Dungeon Game.

Unique Paths: Count paths from top-left to bottom-right moving only right or down.

• State: dp[i][j] = number of ways to reach cell (i,j)
• Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]
• Base case: dp[0][j] = 1 and dp[i][0] = 1
• Complexity: O(mn) time, O(n) space with row optimization

DP Optimization Techniques

Space Optimization Using Rolling Arrays

Many 2D DP solutions only need the previous row (or two rows) to compute the current row. This reduces O(mn) space to O(n) space.

For LCS, Edit Distance, and Unique Paths, you can replace the 2D array with two 1D arrays (current row and previous row), reducing space from O(mn) to O(n).

Common DP Optimization Patterns

Problem Type	Naive Complexity	Optimized	Technique
Fibonacci	O(2^n) recursive	O(n) time, O(1) space	Store only last two values
LCS	O(2^(m+n)) recursive	O(mn) time, O(n) space	2D DP with row optimization
Matrix Chain	O(n!) naive	O(n³) time, O(n²) space	Interval DP
Longest Increasing Subsequence	O(n²) DP	O(n log n)	DP + binary search

Recognizing DP in Interview Problems

These phrases in a problem statement often signal a DP solution:

• "Maximum/minimum" combined with "all possible ways" or "at each step"
• "Number of ways to..."
• "Can you achieve..." (boolean DP)
• "Partition/split into..."
• "Longest/shortest subsequence or substring"
• "Without adjacent" or "with constraints on choices"

When you see these signals, immediately think: what is my state, what is my recurrence, what are my base cases?

---

Frequently Asked Questions

How do I know if I should use DP or greedy algorithms? Both can solve optimization problems. Use DP when local greedy choices do not guarantee a global optimum — typically when the problem has overlapping subproblems and you need to evaluate multiple paths. Use greedy when a locally optimal choice at each step always leads to a globally optimal solution. Activity Selection and Huffman Coding are classic greedy problems; Knapsack and Edit Distance require DP because greedy choices fail.

What is the best way to practice DP problems? Work through problems by category rather than randomly. Start with linear DP (Fibonacci, Climbing Stairs, Coin Change), then 2D DP (LCS, Edit Distance, Unique Paths), then Knapsack variants. Solve each problem independently before looking at solutions, then compare your approach with the standard solution and specifically identify differences in how the state was defined.

Should I always code the bottom-up solution first? Not necessarily. If top-down memoization comes more naturally during the interview, start there. Communicate what you are doing: "I will start with the recursive solution and add memoization." Then, if asked to optimize space, transition to bottom-up. Being able to move between both approaches demonstrates deeper understanding than only knowing one.

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed., Chapter 15: Dynamic Programming). MIT Press.
2. Bellman, R. (1957). Dynamic Programming. Princeton University Press.
3. Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed., Chapter 8). Springer.
4. Gayle Laakmann McDowell. (2015). Cracking the Coding Interview (6th ed., Chapter 8: Recursion and Dynamic Programming). CareerCup.
5. Roughgarden, T. (2020). Algorithms Illuminated, Part 3: Greedy Algorithms and Dynamic Programming. Soundlikeyourself Publishing.