C/C++---------------LeetCode第509. 斐波那契数

2023-12-14 18:49:32

题目及要求

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定 n ,请计算 F(n) 。

示例 1:

输入:n = 2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:

输入:n = 3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3:

输入:n = 4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3

暴力递归

思路:最常见的递归,就是一般老师上课会讲的方法

class Solution {
public:
    int fib(int n) {
       if(n==1||n==2)return 1;
       return fib(n-1)+fib(n-2);
    }
};

备忘录的递归

思路:想要计算原问题 f(20),我就得先计算出子问题 f(19) 和 f(18),然后要计算 f(19),我就要先算出子问题 f(18) 和 f(17)
,这里的f(18)前面已经计算过,在计算f(19)的时候又要计算f(18)大大减小了代码的效率,这个时候可以使用备忘录将前面计算的f(18)保存到备忘录里,下一次计算的时候先去备忘录查看之前有没有计算过这个,如果计算过直接返回结果来用即可

class Solution {
public:
    int fib(int n) {
        if (n < 0) return 0; // 当 n 小于 0 时,直接返回0
        unordered_map<int, int> hash; // 保存已经计算过的斐波那契数列值
        return helper(hash, n); // 调用 helper 函数
    
    int helper(unordered_map<int, int>& hash, int n) {
        if (n == 0 || n == 1) return n; // 当 n 等于 0 或 1 时,直接返回 n
        if (hash.count(n) > 0) { // 如果n在哈希表中存在
            return hash[n]; // 直接返回哈希表中存储的斐波那契数列值
        }
        int res = helper(hash, n - 1) + helper(hash, n - 2); // 递归
        hash[n] = res; // 将计算结果存入哈希表中,以便后续查找使用
        return res; // 返回第 n 个斐波那契数列值
    }
};

动态规划

思路:首先计算a和b的和,将结果保存在sum中,将b的值赋给a,实现向后移动,将sum的值赋给b,更新b的值。
假设输入的数为5的话那么执行过程为
第一轮循环:sum = 0 + 1 = 1,更新a=1,b=1。
第二轮循环:sum = 1 + 1 = 2,更新a=1,b=2。
第三轮循环:sum = 1 + 2 = 3,更新a=2,b=3。
第四轮循环:sum = 2 + 3 = 5,更新a=3,b=5。
第五轮循环:sum = 3 + 5 = 8,更新a=5,b=8。

class Solution {
public:
    int fib(int n) {
        int a = 0, b = 1, sum; // 初始化斐波那契数列的前两个数a和b
        for(int i = 0; i < n; i++){ // 循环计算斐波那契数列的第n个数
            sum = a + b; // 计算下一个数的值
            a = b; // 更新a为上一个数的值
            b = sum; // 更新b为当前计算得到的数的值,实现向后移动
        }
        return a; // 返回斐波那契数列的第n个数
    }
};

文章来源:https://blog.csdn.net/2301_77144243/article/details/134864583
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。