目录
题目概述(简单难度)
思路与代码
思路展现
代码示例
牛客版本
leetcode版本
题目概述(简单难度)
题目链接：
点我进入leetcode
点我进入牛客
思路与代码
思路展现
这道题目大家第一时间会想到我们的递归，虽然思路是正确的，但是有一个缺点就是当斐波那契的数字过多的时候，例如假设我们规定数字个数在0-49之间，使用递归还是勉强可以通过的，但是一旦像本题目这个n是无穷多的话这个时候时间复杂度就会过高，过高在我们对应的这个平台提交的时候就会超出时间限制，所以这个时候我们就要思考了，需要什么方法来去解决这个问题？
于是我们想到了动态规划
下面针对这道题目我们来动态规划仔细解答一下，作为动态规划的入门题目，这道题目也是非常经典的，希望大家可以好好斟酌.
首先动态规划的第一步是定义状态：
首先我们知道问题的本身是求数列第n项的值，那么状态我们就可以设置为数列第i项的值，状态可以设置为F(i),现在我们就要检验我们的状态能否对应到我们的问题,既然是求第n项的值，那么状态就变成了F(n),说明我们的状态设置的没有问题
第二步是定义转移方程，这里的转移方程也是比较明显的，即为F(i) = F(i - 1) + F(i - 2)，但是需要注意的是，转移方程的概念是经过一次就能得到当前状态的方程
第三步是确定我们的初始状态，需要几个初始状态需要看我们的转移方程中到底需要几个状态，例如在我们之前的转移方程F(i) = F(i - 1) + F(i - 2)中就需要两个初始状态，即我们的F(0) = 0,F(1) = 1。
第四步是返回结果，即返回我们的F(n)
代码示例
因为这道题目leetcode和牛客的返回形式不一样，leetcode要求答案取模，而牛客没有要求.
牛客版本
public class Solution { public int Fibonacci(int n) { //首先定义初始状态 int fn0 = 0; int fn1 = 1; //定义一个最终我们存储返回结果的变量fn int fn = 0; if(n <= 1) { return n; } //注意一定是小于等于n for(int i = 2 ; i <= n; i++) { fn = fn0 + fn1; fn0 = fn1; fn1 = fn; } return fn; } }
leetcode版本
class Solution { public int fib(int n) { //首先定义初始状态 int fn0 = 0; int fn1 = 1; //定义一个最终我们存储返回结果的变量fn int fn = 0; if(n <= 1) { return n; } //注意一定是小于等于n for(int i = 2 ; i <= n; i++) { fn = (fn0 + fn1) % 1000000007; fn0 = fn1; fn1 = fn; } return fn; } }
关于取余这段代码的注意事项：
1：
2：就是取余为什么是 1000000007？
答案当然是题目中给的条件啊！！！！！
3：关于这段代码还有最优解，就是使用矩阵快速幂这个解法，这个后期我们再进行跟进.
