Fibonacci
f(n) = f(n-1) + f(n-2). The smallest example of memoization versus tabulation.
DP in One Row: Fibonacci by table
dp[2] = dp[1] + dp[0] = 1 + 0 = 1.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(1)
O(2^n) naive. O(n) memoized. O(1) space with two variables.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
DP in One Row covers these too, in the same run.