DP-LeetCode-509. 斐波那契数

思路：

斐波那契数列明确给出了递推方程（状态转移方程）。

代码语言：javascript复制

f[0] = 0 
f[1] = 1 
n>=2 f[n] = f[n - 1]   f[n - 2]

优化： 一维数组压缩为三个变量，因为从递推方程中观察到当前n的状态至于前一项和前两项相关，所以只需要记录当前项的前两项进行递推即可。

时间复杂度：O(n) 空间复杂度：O(1)

代码

代码语言：javascript复制

class Solution {
public:
    int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int a = 0;
        int b = 1;
        int c = 0;
        n -= 1;
        while (n--) {
            c = a   b;
            a = b;
            b = c;
        }
        return c;
    }
};

变量 数组 压缩 优化

0 人点赞