Nth Fibonacci Time : O(n) Space : O(n) 123456789101112int 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);}