Fibonacci: Memoization and Tabulation

The Fibonacci numbers are F(0) = 0, F(1) = 1, and each later term is the sum of the two before it. Naive recursion recomputes the same F(k) many times; memoization stores each F(k) the first time it is computed so every subproblem is solved once.

Let dp(n) denote the n-th Fibonacci number F(n). For all integers n ≥ 2, the definition of the sequence gives:

Explanation: F(n) is defined as the sum of the two preceding terms. In DP language, the optimal (in fact, only) value for n is obtained entirely from the answers at n − 1 and n − 2 — there is no separate maximization step. The subproblems overlap (e.g. F(n−1) and F(n−2) both need F(n−3)), so memoization removes redundant work.

Use an array memo[0…n]. Treat memo[k] = −1 (or another sentinel) as “not computed yet.” Before you apply the recurrence for dp(n), if memo[n] is already filled, return it immediately. After you compute dp(n) from smaller arguments, store the result in memo[n] before returning.

There are only n + 1 distinct arguments (0 through n), so at most n + 1 real computations — O(n) time with O(n) extra space for memo plus the recursion stack.

The recurrence is only valid for n ≥ 2. The values that stop the recursion are:

Explanation: These match the definition of the sequence. Every recursive chain eventually hits n = 0 or n = 1, so you must handle these before consulting memo (or you can initialize memo[0] and memo[1] up front and still guard on n ≤ 1 in code for clarity).

The same recurrence and bases can be evaluated bottom-up: fill dp[0], dp[1], then dp[2] through dp[n] in order without recursion. That is tabulation; the DP model (recurrence + bases) is unchanged.

Recursive DP with memoization:

Time: O(n) distinct states. Space: O(n) for memo and O(n) call depth for recursion (tabulation avoids deep recursion).