1. Base cases
F(0) and F(1) are already known.
if (n <= 1) return nTyporithm · easy
Fibonacci DP
▷ Interactive algorithm labfibonacci-dpdynamic-programmingtabulationbase-casessequence
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Fibonacci DP
Dynamic Programming
Fibonacci DP stores earlier Fibonacci values so each state is computed once.
The naive recursive version repeats the same calls many times.
Tabulation builds from known base cases upward.
Each new state reads only the two previous states.
Preparing algorithm lab…
01
State: dp[i] is F(i).
02
Base cases: F(0)=0, F(1)=1.
03
Transition: dp[i-1] + dp[i-2].
04
Time O(n), space O(n).
function fibonacciDp(n) {
if (n <= 1) return n;
const dp = 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];
}Read the implementation
Connect each part of the code to the concept before you type.
2. DP table
dp[i] stores the ith Fibonacci value.
const dp = Array(n + 1).fill(0)3. Seed state
Initialize the first non-zero Fibonacci value.
dp[1] = 14. Transition
Each value is the sum of the two previous values.
dp[i] = dp[i - 1] + dp[i - 2]A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.