剑指Offer - 面试题10- I. 斐波那契数列

文章目录

1. 题目2. DP解题3. 面试题 08.01. 三步问题4. LeetCode 509. 斐波那契数

1. 题目

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

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

斐波那契数列由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：输入：n = 2输出：1示例 2：输入：n = 5输出：5提示：0 <= n <= 100

来源：力扣（LeetCode）

链接：https://leetcode-/problems/fei-bo-na-qi-shu-lie-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. DP解题

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

3. 面试题 08.01. 三步问题

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:输入：n = 3 输出：4说明: 有四种走法示例2:输入：n = 5输出：13提示:n范围在[1, 1000000]之间

来源：力扣（LeetCode）

链接：https://leetcode-/problems/three-steps-problem-lcci

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {public:int waysToStep(int n) {if(n==1)return 1;if(n==2)return 2;if(n==3)return 4;vector<long> dp(n+1,0);dp[1] = 1, dp[2] = 2, dp[3] = 4;for(int i = 4; i <= n; ++i)dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%1000000007;return dp[n];}};

4. LeetCode 509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。

该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.给定 N，计算 F(N)。

来源：力扣（LeetCode） 链接：https://leetcode-/problems/fibonacci-number

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

0 ms 8.1 MB