Watch the memoization table fill cell by cell. Each value is computed exactly once using the recurrence dp[i] = dp[i-1] + dp[i-2], turning exponential recursion into linear time.
Input: n = 8
0F(8) = 2120
Max n = 20 (F(20) = 6765). Slider range 0–20.
Playback Controls
Step 1 / 170%
SpeedNormal
Space / Enter: Play·Pause
← →: Step R: Reset
Legend
Base case (dp[0], dp[1])
Source cells being read
Cell being computed
Newly filled
Previously computed
Not yet reached
Time: O(n)
Space: O(n)
Cells filled: 1 / 9
Base Case
Memoization Table — dp[0..8]
dp[0]0
dp[1]?
dp[2]?
dp[3]?
dp[4]?
dp[5]?
dp[6]?
dp[7]?
dp[8]?
dp[0] = 0
base case
Base case: dp[0] = 0 (the 0th Fibonacci number is 0)
Base Cases
dp[0] = 0dp[1] = 1
Recurrence
dp[i] = dp[i-1] + dp[i-2]
for i = 2, 3, …, n
Answer
return dp[n]
F(8) = ?
Reference implementation of Fibonacci — Dynamic Programming. Select a language tab to view and copy the code.
#include <stdio.h>
long long fibonacci(int n) {
if (n <= 1) return n;
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];
}
int main() {
for (int i = 0; i <= 10; i++) {
printf("F(%d) = %lld\n", i, fibonacci(i));
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
long long fibonacci(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];
}
int main() {
for (int i = 0; i <= 10; i++) {
cout << "F(" << i << ") = " << fibonacci(i) << "\n";
}
return 0;
}
public class FibonacciDP {
public static long fibonacci(int n) {
if (n <= 1) return n;
long[] dp = new long[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];
}
public static void main(String[] args) {
for (int i = 0; i <= 10; i++) {
System.out.printf("F(%d) = %d%n", i, fibonacci(i));
}
}
}
def fibonacci(n: int) -> int:
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
for i in range(11):
print(f"F({i}) = {fibonacci(i)}")
function fibonacci(n) {
if (n <= 1) return n;
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
for (let i = 0; i <= 10; i++) {
console.log(`F(${i}) = ${fibonacci(i)}`);
}
Python — Code Walkthrough
1
Initialise the DP list
dp = [0] * (n + 1)
Python list multiplication creates n+1 zeros in one expression. dp[0] = 0 is set implicitly; dp[1] = 1 is assigned on the next line.
2
Seed the first non-trivial base case
dp[1] = 1
Only this one seed assignment is needed after the zero-filled list. Everything else is derived by the loop.
3
Fill using range(2, n + 1)
dp[i] = dp[i - 1] + dp[i - 2]
Python's range(2, n+1) is exclusive of n+1, so the loop visits indices 2, 3, …, n — exactly the cells that need computation.
4
Return the result
return dp[n]
Python integers are arbitrary-precision, so there is no overflow. Fibonacci numbers grow exponentially, but Python handles them natively — you can safely call fibonacci(1000) and get the correct ~210-digit answer.
5
Alternative: O(1) space with tuple swap
a, b = 0, 1
for _ in range(n): a, b = b, a + b
return a
Python tuple unpacking makes the two-variable rolling update particularly elegant. This O(1) space form is idiomatic Python and avoids allocating the list entirely.
Guard the base cases if (n <= 1) return n; F(0) = 0 and F(1) = 1 by definition. Returning early avoids out-of-bounds access when allocating dp[n+1] with n < 2.Allocate the memoization table long long dp[n + 1]; A variable-length array (VLA) of size n+1 holds every sub-result from F(0) to F(n). Using long long prevents integer overflow for large n (Fibonacci numbers grow exponentially).Seed the base cases into the table dp[0] = 0; dp[1] = 1; These two entries are the "seeds" the recurrence depends on. Every subsequent cell is derived from exactly two previously filled cells.Fill the table bottom-up dp[i] = dp[i - 1] + dp[i - 2]; Each iteration reads two already-computed values and writes one new value. Because we always proceed left to right, both dp[i-1] and dp[i-2] are guaranteed to be filled before they are needed — no recursion required.Return the accumulated answer return dp[n]; After the loop, dp[n] holds F(n). Time complexity is O(n) — exactly n-1 additions — and space is O(n) for the dp array. The space can be reduced to O(1) by keeping only two rolling variables.
Use std::vector for safe dynamic sizing vector<long long> dp(n + 1); Unlike C VLAs, std::vector is heap-allocated, bounds-checked in debug builds, and avoids stack overflow for large n. Value-initialization fills every element with 0.Seed base cases dp[0] = 0; dp[1] = 1; Since value-initialization already zeroed the vector, only dp[1] = 1 strictly needs to be set. dp[0] = 0 is written explicitly for clarity.Apply the recurrence left to right dp[i] = dp[i - 1] + dp[i - 2]; The recurrence F(n) = F(n-1) + F(n-2) is applied for every i from 2 to n. Because the loop is strictly ascending, every value on the right-hand side was computed in an earlier iteration.Return the final value return dp[n]; dp[n] is the answer. Returning by value is correct — the vector is not needed after the call. Total time is O(n) with O(n) extra space.Space-optimised variant (O(1) space) long long a = 0, b = 1, c;
for (int i = 2; i <= n; ++i) { c = a + b; a = b; b = c; } Keeping only two rolling variables instead of the full table reduces space to O(1). This is the production-ready variant — the table approach is shown here to make the DP structure explicit.
Declare the DP array with long long[] dp = new long[n + 1]; Java arrays are zero-initialised by default, so dp[0] = 0 is free. Using long (64-bit) handles Fibonacci numbers up to F(92) before overflow.Seed dp[1] dp[1] = 1; dp[0] is already 0 from zero-initialisation. Only dp[1] = 1 must be set explicitly.Iterative bottom-up fill dp[i] = dp[i - 1] + dp[i - 2]; This single line encodes the entire Fibonacci recurrence. The loop runs exactly n-1 times, each time doing one addition and one write — giving O(n) time.Return dp[n] return dp[n]; dp[n] now holds F(n). The method returns a long so callers can handle large values without casting.Why DP beats naive recursion Naive recursive Fibonacci recomputes every sub-problem exponentially — F(5) alone calls F(3) twice, F(2) three times, etc., giving O(2^n) time. Bottom-up DP solves each sub-problem exactly once, dropping time to O(n) and eliminating stack-overflow risk for large n.
Allocate and zero-fill the array const dp = new Array(n + 1).fill(0); Array(n+1) creates a sparse array with holes; .fill(0) makes every element a true 0. This is important because uninitialized holes would produce NaN in arithmetic.Seed dp[1] dp[1] = 1; dp[0] is already 0 from .fill(0). Setting dp[1] = 1 completes the two seed values the recurrence needs.Iterative fill with for loop dp[i] = dp[i - 1] + dp[i - 2]; JavaScript numbers are IEEE-754 doubles, which represent integers exactly up to 2^53 - 1. Fibonacci values exceed this around F(79). For large n, switch to BigInt: const dp = Array(n+1).fill(0n); dp[1] = 1n;Return the answer return dp[n]; dp[n] holds F(n) after the loop. Time is O(n), space is O(n). The entire function body is 6 lines — concise yet clear thanks to the explicit DP table.Memoized top-down variant const memo = {};
function fib(n) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
return memo[n] = fib(n-1) + fib(n-2);
} The top-down memoized approach uses an object as a cache. Each sub-problem is computed at most once. It trades the explicit table for implicit recursion depth — both are O(n) time and space. Bottom-up is generally preferred in production to avoid stack overflow.