「LeetCode」509-斐波那契数⚡️

简介: 「LeetCode」509-斐波那契数⚡️

image.png

前言🌧️


算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。


因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。


编写指令的好坏,会直接影响到程序的性能优劣,而指令又由数据结构和算法组成,所以数据结构和算法的设计基本上决定了最终程序的好坏


题目🦀



509. 斐波那契数


难度简单


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


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

提示:

  • 0 <= n <= 30

解题思路🌵



  • 利用动态规划来求解此题
  • 如果每一次结果都和前几次叠加的问题,那么就可以考虑动态规划


解题步骤🐂



  • 初始化dp数组
  • 遍历数组
  • 记录dp[i]的值 dp[i]=dp[i-1]+dp[i-2]
  • 最后返回dp[n]


源码🔥



/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    const dp=[0,1]
    for(let i=2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2]
    }
    return dp[n]
};

时间复杂度:O(n)


空间复杂度:O(1)


结束语🌞



image.png

image.png


那么鱼鱼的LeetCode算法篇的「LeetCode」509-斐波那契数⚡️ 就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾,欢迎加我好友,一起沙雕,一起进步

相关文章
|
6月前
|
Java
leetcode-509:斐波那契数
leetcode-509:斐波那契数
478 0
|
3月前
|
Python
【Leetcode刷题Python】509. 斐波那契数
LeetCode第509题"斐波那契数"的两种Python解决方案:一种是递归方法,另一种是使用滚动数组的迭代方法,以计算第n个斐波那契数。
27 2
|
6月前
|
Go
golang力扣leetcode 509.斐波那契数
golang力扣leetcode 509.斐波那契数
31 0
|
11月前
leetcode 509 斐波那契数
今天重新看了下动态规划, 它和递归的区别就是,它是自下而上的。 还了解到状态压缩 如果我们发现每次状态转移只需要 DP table 中的一部分,那么可以尝试用状态压缩来缩小 DP table 的大小,只记录必要的数据 于是就刷了这道简答题,用到了状态压缩
38 0
|
12月前
|
算法
代码随想录算法训练营第三十八天 | LeetCode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
代码随想录算法训练营第三十八天 | LeetCode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
48 0
|
12月前
LeetCode题:70爬楼梯,126斐波那契数
LeetCode题:70爬楼梯,126斐波那契数
54 0
【Leetcode -509.斐波那契数 -520.检测大写字母】
【Leetcode -509.斐波那契数 -520.检测大写字母】
51 0
leetcode 509 斐波那契数
leetcode 509 斐波那契数
77 0
leetcode 509 斐波那契数
|
API Python
力扣刷题记录——507.完美数、509. 斐波那契数、520. 检测大写字母
力扣刷题记录——507.完美数、509. 斐波那契数、520. 检测大写字母
142 0
力扣刷题记录——507.完美数、509. 斐波那契数、520. 检测大写字母
代码随想录刷题|动态规划理论基础 LeetCode 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯(下)
代码随想录刷题|动态规划理论基础 LeetCode 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯
代码随想录刷题|动态规划理论基础 LeetCode 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯(下)