What Is Dynamic Programming?
Dynamic programming (DP) is one of the most powerful and frequently tested algorithm paradigms in computer science. At its core, DP is a technique for solving complex problems by breaking them down into overlapping subproblems and storing results to avoid redundant computation.
If you've ever solved a Fibonacci problem recursively and noticed your function re-computing the same values over and over, you've already seen the problem DP solves.
The Two Pillars: Memoization vs. Tabulation
There are two primary approaches to implementing dynamic programming:
- Top-Down (Memoization): Start with the original problem, recurse into subproblems, and cache results as you go.
- Bottom-Up (Tabulation): Build solutions to all subproblems from the smallest case upward, filling a table iteratively.
Both approaches yield the same results, but they differ in code style and sometimes in practical performance. Memoization is often more intuitive to write; tabulation is typically more memory-efficient.
Step-by-Step: Fibonacci With DP
The classic example to illustrate DP is computing Fibonacci numbers.
Naive Recursion (Exponential Time)
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)This runs in O(2ⁿ) time — catastrophically slow for large inputs.
Memoized Version (O(n) Time)
def fib(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]Tabulated Version (O(n) Time, O(n) Space)
def fib(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Recognizing a DP Problem
Not every problem needs DP. Here's how to spot one:
- Optimal substructure: The optimal solution can be built from optimal solutions to subproblems.
- Overlapping subproblems: The same subproblems are solved multiple times in a naive recursive approach.
Common problem types that benefit from DP include: knapsack problems, coin change, longest common subsequence, shortest path in DAGs, and matrix chain multiplication.
Common DP Patterns to Learn
| Pattern | Example Problems |
|---|---|
| Linear DP | Fibonacci, House Robber |
| Grid DP | Unique Paths, Minimum Path Sum |
| Interval DP | Burst Balloons, Matrix Chain |
| Knapsack DP | 0/1 Knapsack, Subset Sum |
| String DP | Longest Common Subsequence, Edit Distance |
Tips for Solving DP Problems
- Define your state clearly — what does
dp[i]represent? - Write the recurrence relation before coding.
- Identify base cases and handle edge cases early.
- Start with memoization if bottom-up feels unclear.
- Optimize space only after correctness is confirmed.
Next Steps
Once you're comfortable with Fibonacci-style DP, move on to the 0/1 Knapsack problem and Longest Common Subsequence (LCS) — these two cover the vast majority of DP interview questions you'll encounter. Practice on LeetCode's "Dynamic Programming" tag, starting with Easy and Medium problems.