Fibonacci Number
LeetCode https://leetcode.cn/problems/fibonacci-number/
- Recursive
1
2
3
4
5
6
7
8
9
10
class Solution {
public int fib(int n) {
// base case
if (n == 0 || n == 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
}
Complexity
- Time = O(2^n)
- Space = O(n)
- DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int fib(int n) {
if (n == 0 || n == 1) {
return n;
}
int[] dp = new int[n+1]; // sub-solutions
dp[0] = 0; // base case
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
Complexity
- Time = O(n)
- Space = O(n)
This post is licensed under CC BY 4.0 by the author.