本文共 1842 字，大约阅读时间需要 6 分钟。

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）

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）

class Solution {
   public:    int waysToStep(int n) {
           if(n==1)            return 1;        if(n==2)            return 2;        if(n==3)            return 4;        vector
   
     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) 表示，形成的序列称为斐波那契数列。

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/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

转载地址：https://michael.blog.csdn.net/article/details/104272616 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！