[AlgoExpert] Nth Fibonacci

Nth Fibonacci

  • Time : O(n)
  • Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
int fib(int n, vector<int>& dp) {
if(dp[n] != -1) return dp[n];
return dp[n] = fib(n-1, dp) + fib(n-2, dp);
}

int getNthFib(int n) {
vector<int> dp(n + 1, -1);
dp[0] = 0, dp[1] = 1;

return fib(n - 1, dp);
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/09/PS/AlgoExpert/nth-fibonacci/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.