Search
4 results for “dynamic-programming”
Search results
Dynamic Programming
Why caching subproblem solutions turns an exponential naive recursive Fibonacci into a linear one, and what "overlapping subproblems" actually has to be true about a problem before memoization can help at all.
What does NIST's own definition of dynamic programming actually say the technique does, and what problem does it solve?
NIST's Dictionary of Algorithms and Data Structures defines dynamic programming as an algorithmic technique to "solve an optimization problem by caching subproblem solutions (memoization) rather than recomputing them." The problem it solves is redundant recomputation: when a naive recursive solution calls itself with the same subproblem arguments repeatedly (matrix-chain multiplication, longest common subsequence, and similar problems are the examples NIST gives), that same subproblem gets solved from scratch every single time it recurs, and caching the first result lets every later occurrence be a lookup instead of a full recomputation.
Why does a naive recursive Fibonacci function run in exponential time, and how does memoization fix that specifically?
Naive recursive `fib(n) = fib(n-1) + fib(n-2)` recomputes the exact same subproblem enormous numbers of times, `fib(n-2)` gets computed once directly and once again inside the `fib(n-1)` call, and this duplication compounds recursively, producing roughly 2^n total calls. Memoization caches each `fib(k)` result the first time it's computed, so every subsequent call with the same `k` becomes an O(1) cache lookup instead of a full recursive recomputation, collapsing the total distinct work down to O(n), one computation per distinct subproblem instead of an exponential number of repeated ones.
What does "overlapping subproblems" mean, and why does dynamic programming provide no benefit for a problem that lacks it?
Overlapping subproblems means the same smaller subproblem genuinely recurs multiple times across different branches of the larger problem's recursive structure, exactly what makes caching valuable, the second and later occurrences become free lookups. A problem like standard mergesort, by contrast, has no overlapping subproblems, every recursive call operates on a genuinely distinct slice of the array that never recurs anywhere else, so there is nothing to cache and memoization adds only overhead (cache storage and lookup cost) with zero reuse to offset it. Recognizing whether a problem's recursive breakdown actually revisits the same subproblems is the real prerequisite for dynamic programming to help at all.