Fibonacci

// normal solution (no DP)
// time: O(2^n), space: O(n)
int std_fibonacci(int n) {
	if (n <= 1)
		return n;
	return std_fibonacci(n - 1) + std_fibonacci(n - 2)
}
 
// Bottom Up Method
// time: O(n), space: O(n)
int btmUp_fibonacci(int n) {
	vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
 
// Top Down Method
// time: O(n), space: O(n)
int fib(vector<int> &dp, int n) {
	if (n <= 1)
		return n;
	if (dp.at(n) != 0) // check if this was already computed
		return dp.at(n); 
	dp.at(n) = fib(dp, n - 1) + fib(dp, n - 2);
	return dp.at(n);
}
 
int topDown_fibonacci(int n) {
    vector<int> dp(n + 1, 0);
    return fib(dp, n);
}