剑指Offer 10-Ⅰ.斐波那契数列

发布于 2021-09-08 11:07 ，所属分类：数学资料学习库

Conceitedpeopleneverhearanythingbutpraise.爱慕虚荣的人只听得见赞扬声。

前言

利用「尾递归」、「动态规划」和「递推」来解决问题。

剑指Offer 10-Ⅰ.斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1

F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例：

输入：n=2

输出：1

尾递归

一开始直接用普通递归做，n稍微大一点的时候就超出时间限制了，于是想到「尾递归」

递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，因此递归次数过多容易造成栈溢出。

尾递归是把当前的运算结果放在参数里传递给下层函数，只用保存最后一个函数堆栈。

代码如下：

class Solution { public:    int fib(int n) {        return fibTail(n,0,1);    }    int fibTail(int n,int curr,int next){        int mod = 1e9+7;        if(n==0)            return curr;        return fibTail(n-1,next%mod,(curr+next)%mod);    }};

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

动态规划

题中已经给出了状态转移方程

F(N) = F(N - 1) + F(N - 2)

与n值对应，n 是从 0 开始的，我们申请一个大小为 n+1 的数组 dp，

定义 dp[i] 为斐波那契数列第 i 项的值，

那么 dp[n] 为斐波那契数列第 n 项的值，

dp[0]=0 和 dp[1]=1 为两个初始状态，

利用 dp[i] = dp[i-1] + dp[i-2]循环计算dp[i]的值。

代码如下：

class Solution { public:    int fib(int n) {        if(n<=1)            return n;        int mod = 1e9+7;        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];            dp[i] %= mod;        }        return dp[n];    }};

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

递推

根据 F(N) = F(N - 1) + F(N - 2)，我们知道 F(N) 的值只与 F(N - 1) 和 F(N - 2) 有关，那就可以用递推来实现动态规划，也就不需要申请一个数组来保存过程中的值，我们只申请三个常量即可。

代码如下：

class Solution { public:    int fib(int n) {        if(n<=1)            return n;        int mod = 1e9+7;        int a = 0,b = 1;        int sum = a + b;        for(int i=2;i<n;++i){            a = b;            b = sum;            sum = (a + b)%mod;        }        return sum;    }};