本文主要是介绍剑指 Offer 10- I. 斐波那契数列 (Easy),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目
1、题目描述
写一个函数,输入 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
2、基础框架
class Solution {
public:int fib(int n) {}
};
3、原题链接
剑指 Offer 10- I. 斐波那契数列
二、解题报告
1、思路分析
(1)使用动态规划
2、时间复杂度
O ( n ) O(n) O(n)
3、代码详解
class Solution {
public:int fib(int n) {int f[120] = {0, 1};for (int i = 2; i <= n; i++) {f[i] = (f[i - 1] + f[i - 2]) % 1000000007;}return f[n];}
};
这篇关于剑指 Offer 10- I. 斐波那契数列 (Easy)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!