Fibonacci (Dynamic Programming)
1/0
1.0x
Fibonacci (Dynamic Programming)
O(n)
Space: O(n)
Pseudocode
1
procedure fibonacci(n)
2
create table dp[0..n]
3
dp[0] ← 0
4
dp[1] ← 1
5
for i ← 2 to n do
6
dp[i] ← dp[i-1] + dp[i-2]
7
return dp[n]
Random Input