Dynamic Programming· 15 min

Bottom-up Fibonacci (DP)

Iterative DP — fill the table from smallest to largest

Setup

n:
Step 1 / 16

Current step

1 / 16

Initialize dp[0] = 0, dp[1] = 1 (base cases).

Step log

n=00
n=11
n=2?
n=3?
n=4?
n=5?
n=6?
n=7?
n=8?
Computing now
Dependencies used
Filled
Empty
fib.java
1int fib(int n) {
2    if (n <= 1) return n;
3    int[] dp = new int[n + 1];
4    dp[0] = 0; dp[1] = 1;
5    for (int i = 2; i <= n; i++) {
6        dp[i] = dp[i-1] + dp[i-2];
7    }
8    return dp[n];
9}
● Java

Bottom-up Fibonacci

Compute the nth Fibonacci number iteratively. Each value is the sum of the previous two — store them in a 1D table to avoid recomputation.

Time
O(n)
Space
O(n)
Rows
1
Cols
9
39 / 46