天津建站网,江苏省建设工程管理局网站,平面设计培训班多少钱,wordpress 权限问题目录 题目地址#xff1a; 我们直接看题解吧#xff1a; 解题方法#xff1a; 难度分析#xff1a; 审题目事例提示#xff1a; 解题思路#xff08;动态规划#xff09;#xff1a; 代码实现#xff1a; 补充说明#xff1a; 代码#xff08;优化#xff09;…目录 题目地址 我们直接看题解吧 解题方法 难度分析 审题目事例提示 解题思路动态规划 代码实现 补充说明 代码优化 题目地址 LCR 126. 斐波那契数 - 力扣LeetCode 难度简单 今天刷斐波那契数列大家有兴趣可以点上看看题目要求试着做一下。
我们直接看题解吧
解题方法 方法1递归效率太慢 会出现重复例如f(5)f(4)f(3),f(4)f(3)f(2),此时f(3)重复了此外若递归过深则会造成栈溢出情况。 方法2递推动态规划或循环求余 难度分析 总体应该不算难毕竟一般学校应该会用递归法讲这到题 审题目事例提示
答案需要取模 1e97(1000000007) 如计算初始结果为1000000008请返回 1。 解题思路动态规划 由于斐波那契数列是0,1,1,2,3,5,8....即从0 开始通过循环逐步求出下一位数n(n-1)(n-2),通过一个变量sum保存类似于递增因此不会出现重复的情况 代码实现
class Solution {public int fib(int n) {if(n 0){ //判断若n0直接返回0return 0;}int a 0,b 1,sum 0;for(int i 0;i n;i){sum (a b) % 1000000007; //循环取模a b;b sum; //sum相当于存不断累加的结果} return sum;}
}
补充说明 为什么res要模1000000007 因为这个数字是10位的最小质数上面的代码并没有问题只是数字太大会造成溢出需要将计算结果 % 1000000007才能保证得出的结果在int 范围中 代码优化
public int fib(int n) {int a0, b1,sum0;// 当n1时才会进入循环所以for循环算的是n从2到n1的值for(int i2; in1; i){sum(ab) % 1000000007; ab;bsum; }// 由于多算一次所以返回的是a不是breturn a;}
