📘 Introduction to Dynamic Programming
🧩 1. What Is Dynamic Programming?
Dynamic Programming (DP) is a way to solve problems by breaking them into overlapping subproblems and storing results of those subproblems to avoid recalculating them.
In short:
DP = Recursion + Memoization
It’s like remembering the answers to puzzles you’ve already solved so you don’t waste time re-solving them.
💭 2. The Core Idea: Overlapping Subproblems + Optimal Substructure
🔁 Overlapping Subproblems
A problem has overlapping subproblems if you solve the same smaller problems repeatedly.
Example: Fibonacci Numbers
fib(n) = fib(n-1) + fib(n-2)
When you compute fib(5), you end up recalculating fib(3) multiple times.
🧱 Optimal Substructure
A problem has optimal substructure if the optimal solution can be built using the optimal solutions of its subproblems.
Example:
The shortest path to a city = shortest path to its previous city + cost to travel between them.
⚙️ 3. Two Key Techniques in DP
| Approach | Description | Example |
|---|---|---|
| Top-Down (Memoization) | Solve recursively and cache results to avoid recomputation. | Recursive Fibonacci with a memo dict |
| Bottom-Up (Tabulation) | Build up a table (array) iteratively from smallest subproblems. | Iterative Fibonacci using a loop |
Let’s look at both with Fibonacci:
🧮 Example: Fibonacci Numbers
🔹 Top-Down (Memoization)
def fib(n, memo={}):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
print(fib(10)) # Output: 55
🔹 Bottom-Up (Tabulation)
def fib(n):
dp = [0, 1]
for i in range(2, n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]
print(fib(10)) # Output: 55
✅ Both versions produce the same result, but:
-
Top-Down is intuitive if you think recursively.
-
Bottom-Up is efficient and often used in interviews.
🕵️ 4. How to Identify a DP Problem
If you can say “to solve this big problem, I can combine solutions of smaller subproblems”, then it’s a DP problem.
Ask yourself these 3 questions:
-
Can the problem be broken down into subproblems?
-
Do subproblems overlap?
-
Can you find the optimal solution using solutions to smaller subproblems?
✅ If yes to all — it’s a DP candidate.
🧠 5. The 5-Step Process to Solve DP Problems
| Step | Description |
|---|---|
| 1️⃣ | Define subproblem — What does dp[i] represent? |
| 2️⃣ | Identify base cases — What’s the simplest input you can directly solve? |
| 3️⃣ | Find recurrence relation — How can you build dp[i] from smaller subproblems? |
| 4️⃣ | Decide approach — Top-down or bottom-up |
| 5️⃣ | Implement and test |
🔍 6. Key Mindset
DP is not about memorizing formulas — it’s about thinking recursively and then optimizing with memory.
“If brute force works but is slow, DP can make it fast.”
📝 Suggested Practice Problems
Easy
Medium
Hard