DSA TrainerFoundations · Unit 16
Dynamic Programming
Dynamic programming is the topic people brace themselves for, the one that sounds like advanced math. It is not. Strip away the intimidating name and dynamic programming is one plain idea: if your solution keeps solving the same smaller problem over and over, solve it once, write down the answer, and look it up next time instead of recomputing it.
That is the whole trick. The fancy name just means "remember your subresults so you do not redo work." Done well, it turns a recursive solution that would take longer than the age of the universe into one that finishes instantly, by cutting out the repeated effort.
The classic teaching example is Fibonacci, and this unit uses it to show the repeated-work problem, the fix (memoization), and the speedup. Most importantly, it covers how to recognize when a new problem is secretly a dynamic programming problem.
You’re not signed in. Your progress here won’t be saved.
The problem: recursion that redoes work
Fibonacci is defined so each number is the sum of the two before it: fib(n) = fib(n - 1) + fib(n - 2). Translate that straight into recursion and it works, but watch what it computes.
To get fib(5) you need fib(4) and fib(3). But fib(4) also needs fib(3), so fib(3) gets computed twice. And fib(3) needs fib(2), which gets computed again and again across all these branches. As n grows, the same small values get recomputed an explosion of times. The naive recursion is O(2^n), doubling its work with each step up, which is unusable past small n.
Why is the naive recursive Fibonacci (fib(n) = fib(n-1) + fib(n-2)) so slow for larger n?
The drills and graded test are premium
The lessons above are free. The interactive practice that turns recognizing the pattern into recalling it on a blank page unlocks with premium:
- ✓2 applied drills: train spotting when the concept applies
- ✓A 5-question graded test to clear the unit
- ✓The full guided problem ladder with faded hints, plus the cold-read capstone
From $6/month. Cancel anytime.