Dynamic programming
General · Mathematics
Study notes
Q: Use DP to compute fib(5). How many distinct subproblems vs naive recursion? Naive: fib(5) calls fib(4)+fib(3)...: exponential (~15 calls). DP memo: fib(0..5): 6 subproblems, each once: O(n)! Table: 0,1,1,2,3,5: fib(5) = 5! Bellman: optimal = best of subproblems! (DP: remember, don't recompute!)