Nth Fibonacci

• Time : O(n)
• Space : O(n)

c++

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);
}