The naive recursive Fibonacci has exponential time complexity due to overlapping subproblems. Dynamic programming solves this by storing computed values. Memoization (top-down) caches results on first computation. Tabulation (bottom-up) fills a table iteratively. Both achieve O(n) time.
// Bottom-up tabulation
long long fib(int n) {
if (n<=1) return n;
vector<long long> dp(n+1);
dp[0]=0; dp[1]=1;
for(int i=2;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];
return dp[n];
}The recursive formula F(n)=F(n-1)+F(n-2) recomputes F(2)...F(n-2) exponentially many times. DP avoids this by storing each subproblem result once.
Bottom-up tabulation fills dp[0..n] iteratively — simpler and cache-friendly. Top-down memoization uses recursion with a cache — easier to adapt when not all subproblems are needed.
Since F(n) only depends on F(n-1) and F(n-2), we only need two variables, reducing space from O(n) to O(1): a,b=0,1; for _ in range(n): a,b=b,a+b.
Quiz coming soon for this algorithm.