LeetCode 509 斐波那契数

动态规划

const int N  = 40;
class Solution {
public:
    int dp[N];
    int fib(int n) {
        dp[1] = 1;

        for (int i = 2; i <= n; i ++)
            dp[i] = dp[i - 1] + dp[i - 2];

        return dp[n];
    }
};

动态规划压缩到维护两个值

class Solution {
public:
    int dp[2];
    int fib(int n) {
        if (n <= 1) return n;
        
        dp[1] = 1;

        for (int i = 2; i <= n; i ++) {
            int temp = dp[1];
            dp[1] = dp[0] + dp[1];
            dp[0] = temp;
        }

        return dp[1];

    }
};

递归

class Solution {
public:
    int fib(int n) {
        if (n == 0) return 0;

        if (n == 1) return 1;

        return fib(n - 1) + fib(n - 2);
    }
};