Dynamic Programming — How to Approach DP Interview Problems
The Interview Question
How do you approach a dynamic programming problem? Walk me through your framework.
Expert Answer
Dynamic programming solves problems by breaking them into overlapping subproblems and caching the results so each subproblem is solved only once. The framework has four steps. First, identify the subproblem — what's the 'state' that defines a smaller version of the problem? For fibonacci, it's f(n-1) and f(n-2). For the knapsack problem, it's 'maximum value using items 1..i with capacity w'. Second, write the recurrence relation — how does the answer to the current problem relate to the answers of subproblems? Third, choose your approach — top-down (recursion + memoization) is usually easier to write and closer to the recurrence, while bottom-up (iterative table-filling) avoids recursion overhead and makes space optimization possible. Fourth, optimize space if needed — many DP problems only need the previous row/column, not the entire table. The hardest part is step 1: seeing that a problem has optimal substructure (the optimal solution contains optimal solutions to subproblems) and overlapping subproblems (the same subproblems are solved repeatedly).
Key Points to Hit in Your Answer
- Framework: subproblem → recurrence → memoize/tabulate → optimize
- Top-down (memoization): recursive, easier to derive, may hit stack limits
- Bottom-up (tabulation): iterative, no stack overflow, enables space optimization
- Optimal substructure + overlapping subproblems = DP candidate
- If subproblems don't overlap, it's just recursion (divide and conquer)
- Common DP families: sequence (LIS, LCS), knapsack, interval, grid path, tree DP
- Space optimization: often O(n²) → O(n) by keeping only previous row
Code Example
# Classic: Climbing Stairs (fibonacci variant)
# Subproblem: ways(i) = ways to reach step i
# Recurrence: ways(i) = ways(i-1) + ways(i-2)
# Top-down (memoization)
def climb_memo(n, memo={}):
if n <= 2: return n
if n in memo: return memo[n]
memo[n] = climb_memo(n - 1) + climb_memo(n - 2)
return memo[n]
# Bottom-up (tabulation)
def climb_tab(n):
if n <= 2: return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# Space-optimized (only need last 2 values)
def climb_opt(n):
if n <= 2: return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1
# 0/1 Knapsack
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w] # skip item
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1]) # take item
return dp[n][capacity]What Interviewers Are Really Looking For
DP is the most feared interview topic. The interviewer wants to see a systematic approach, not trial and error. Start by defining the state clearly ('dp[i] represents...'), write the recurrence before coding, then implement. Showing the progression from memoized → tabulated → space-optimized on climbing stairs demonstrates mastery of the full DP toolkit.
Practice This Question with AI Grading
Reading about interview questions is a start — but practicing with real-time AI feedback is how you actually get better. Goliath Prep grades your answers instantly and tells you exactly what you're missing.
Start Practicing Free →