LeetCode刷题--点滴记录016

短命女 2023-09-28 11:13 1阅读 0赞

## 16. 剑指 Offer 10-I. 斐波那契数列 ##

**要求**

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

**思路**

动态规划方法：

*  状态定义： 设 dp为一维数组，其中 dp\[i\]的值代表 斐波那契数列第 i个数字
 *  转移方程： dp\[i\] = dp\[i - 1\] + dp\[i - 2\]，即对应数列定义 f(n) = f(n - 1) + f(n - 2)
 *  初始状态： dp\[0\] = 0, dp\[1\] = 1，即初始化前两个数字
 *  返回值： dp\[n\]，即斐波那契数列的第 n 个数字

**解题**

#include <iostream>
    using namespace std;
    #include <vector>
    
    class Solution {
        
    public:
        int fib(int n) {
        
            if (n == 0) {
        
                return 0;    // 若求 f(0) 则直接返回 0 ,初始化 f(0)
            }
            vector<int> dp(n + 1, 0);  // 初始化 dp 列表
            dp[1] = 1;                 // 初始化 f(1)
            for (int i = 2; i <= n; i++) {
        
                dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;  // 状态转移求取 f(2), f(3), ..., f(n) 
            }
            return dp[n];  // 返回f[n]
        }
    };
    
    void test01()
    {
        
        Solution s;
        for (int i = 0; i < 10; i++) {
        
            int f = s.fib(i);
            cout << f << " ";
        }
        cout << endl;
    
    }
    
    int main()
    {
        
        test01();
    
        system("pause");
        return 0;
    }

![在这里插入图片描述][c8567ecf82764a6384a7aa210fdec970.png_pic_center]

**希望本文对大家有帮助，上文若有不妥之处，欢迎指正**

**分享决定高度，学习拉开差距**

[c8567ecf82764a6384a7aa210fdec970.png_pic_center]: https://img-blog.csdnimg.cn/c8567ecf82764a6384a7aa210fdec970.png#pic_center