What is Dynamic Programming?
Learn dynamic programming — optimal substructure, overlapping subproblems, memoization vs tabulation — with a Fibonacci example and DSA interview questions.
Expected Interview Answer
Dynamic programming is a technique for solving problems by breaking them into overlapping subproblems and storing each subproblem’s result so it is computed only once, trading memory for a large reduction in repeated work.
DP applies when a problem has optimal substructure (the optimal solution is built from optimal solutions to subproblems) and overlapping subproblems (the same subproblems recur). Two styles: top-down memoization (recursion plus a cache) and bottom-up tabulation (fill a table iteratively). Classic examples — Fibonacci, longest common subsequence, knapsack — go from exponential brute force to polynomial time by reusing stored results.
- Turns exponential recomputation into polynomial time
- Memoization and tabulation are two clear styles
- Solves optimization and counting problems elegantly
AI Mentor Explanation
Dynamic programming is like keeping a running ball-by-ball record so you never recompute a partnership’s total from scratch — each new ball just adds to the stored subtotal. Without it, recalculating totals repeatedly wastes huge effort (the exponential brute force). DP stores each subproblem’s answer once and reuses it, exactly like a scorer building on saved subtotals instead of re-adding every delivery.
Step-by-Step Explanation
Step 1
Check the two properties
Optimal substructure and overlapping subproblems must both hold.
Step 2
Define the state
Identify what parameters uniquely describe a subproblem.
Step 3
Write the recurrence
Express a state’s answer in terms of smaller states.
Step 4
Memoize or tabulate
Cache results top-down, or fill a table bottom-up.
What Interviewer Expects
- Optimal substructure + overlapping subproblems as the trigger
- Memoization vs tabulation
- A classic example (Fibonacci, LCS, knapsack)
- The time/space complexity improvement over brute force
Common Mistakes
- Applying DP without overlapping subproblems (use divide-and-conquer instead)
- Getting the state definition or recurrence wrong
- Forgetting base cases
- Confusing DP with plain recursion (no caching)
Best Answer (HR Friendly)
“Dynamic programming solves complex problems by breaking them into smaller repeating subproblems and remembering each subproblem’s answer so it’s solved only once. That reuse turns slow, exponential solutions into fast ones — used for problems like shortest paths and the knapsack problem.”
Code Example
# Exponential without caching
def fib_slow(n):
return n if n < 2 else fib_slow(n-1) + fib_slow(n-2)
# O(n) with memoization
def fib(n, memo={}):
if n < 2:
return n
if n not in memo:
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
print(fib(50)) # instantFollow-up Questions
- What is the difference between memoization and tabulation?
- When is greedy better than DP?
- What is optimal substructure?
- How do you reduce the space complexity of a DP solution?
MCQ Practice
1. Dynamic programming requires which two properties?
DP applies when optimal solutions build from subproblems that recur (overlap).
2. Top-down DP with a cache is called?
Memoization is recursion plus a cache; tabulation fills a table bottom-up.
3. DP mainly trades what for speed?
Storing subproblem results uses extra memory to avoid recomputation.
Flash Cards
When to use DP? — Optimal substructure + overlapping subproblems.
Memoization? — Top-down recursion with a cache of subproblem results.
Tabulation? — Bottom-up: fill a table of subproblem answers iteratively.
What does DP trade? — Memory for a large reduction in repeated computation.