力扣 509. 斐波那契数

这篇具有很好参考价值的文章主要介绍了力扣 509. 斐波那契数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目来源:https://leetcode.cn/problems/fibonacci-number/description/

力扣 509. 斐波那契数,开始C++吧,leetcode,算法,c++,动态规划

力扣 509. 斐波那契数,开始C++吧,leetcode,算法,c++,动态规划 

 C++题解1:根据题意,直接用递归函数。

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

C++题解2(来源代码随想录):动态规划。动规五部曲:这里我们要用一个一维dp数组来保存递归的结果。

  1. 确定dp数组以及下标的含义:dp[i]的定义为第i个数的斐波那契数值是dp[i]
  2. 确定递推公式:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
  3. dp数组如何初始化:dp[0] = 0; dp[1] = 1;
  4. 确定遍历顺序:从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的
  5. 举例推导dp数组:按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2],我们来推导一下,当N为10的时候,dp数组应该是如下的数列:0 1 1 2 3 5 8 13 21 34 55
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        vector<int> dp(N + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }
};

C++题解3(来源代码随想录):动态规划。只需要维护两个数值就可以了,不需要记录整个序列。文章来源地址https://www.toymoban.com/news/detail-618241.html

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

到了这里,关于力扣 509. 斐波那契数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包