Solving problems by remembering past results
Day 93 of 149
👉 Full deep-dive with code examples
The Homework Analogy
Doing homework, you keep solving the same sub-problem:
Dumb approach: Recalculate every time
Smart approach: Write down answers, look them up!
Dynamic Programming = remembering solutions you've already computed.
The Classic Example: Fibonacci
# Bad: Recalculates the same values constantly
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2) # fib(3) calculated 10x!
# Good: Remember what we calculated
def fib(n, memo={}):
if n in memo: return memo[n] # Already solved!
if n <= 1: return n
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
From O(2^n) → O(n)! Exponentially faster!
For larger n, this is typically much faster.
When to Use DP
Two conditions:
- Overlapping subproblems: Same calculations repeat
- Optimal substructure: A good overall solution can be built from good sub-solutions
Famous DP Problems
| Problem | Description |
|---|---|
| Fibonacci | Sum of previous two |
| Knapsack | Maximize value with weight limit |
| Edit Distance | Minimum edits to transform string |
| Coin Change | Minimum coins for amount |
The Power
Without DP: Some problems can take a very long time
With DP: The same problems can become fast enough to run in practice
In One Sentence
Dynamic Programming solves problems by storing solutions to sub-problems and reusing them.
🔗 Enjoying these? Follow for daily ELI5 explanations!
Making complex tech concepts simple, one day at a time.
Top comments (0)