题目

题目链接
剑指offer：斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

解题思路

斐波那契数列属于经典的递归问题，对于这题的求解，我们首先要知道斐波那契数列的状态转移式，即f[n]=f[n-1]+f[n-2]，且在n=1或2时，f[n]=1。
在理解基础的状态转移式后，最容易想到的便是递归调用，但很遗憾，这样算法的时间复杂度往往达不到要求。
仔细观察后可以发现，每次求解的f[n]都在之后两个f[n]的求解中起作用，因此我们可以将其保存，这样能够避免重复计算，降低算法的时间复杂度；同时，因为只在后续两个f[n]的求解中起作用，因此只需要保存两个f[n]的值即可。

具体代码

class Solution {
public:
    int Fibonacci(int n) {
        int num[3];
        // num[0]和num[1]分别表示f[n-2]和f[n-1]
        num[0] = 0;
        num[1] = 1;
        if (n < 2)
            return num[n];
        // 计算n>2时数列的值
        for (int i = 2; i <=n; i++) {
            num[2] = num[0] + num[1];
            // 更新f[n-2]和f[n-1]
            num[0] = num[1];
            num[1] = num[2];
        }
        return num[2];
    }
};

剑指offer：斐波那契数列

原文：https://www.cnblogs.com/Bylight/p/10628008.html