网站租金可以做办公费吗,软件开发工资高吗,建设银行储蓄卡申请网站,wordpress搬家后题目链接#xff1a;509. 斐波那契数
题目描述
斐波那契数 #xff08;通常用 F(n) 表示#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a;
F(0) 0#xff0c;F(1) 1
F(n) F(n -…题目链接509. 斐波那契数
题目描述
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(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
文章讲解代码随想录
视频讲解手把手带你入门动态规划 | LeetCode509.斐波那契数_哔哩哔哩_bilibili
题解1动态规划
思路使用动态规划的思路来求解本题学习动态规划的基本思路。
动态规划分析
dp 数组以及下标的含义dp[i] 为第 i 个斐波那契数。递推公式dp[i] dp[i - 1] dp[i - 2]。dp 数组初始化dp[0] 0dp[1] 1。遍历顺序从前向后。打印 dp 数组0、1、1、2、3、......
/*** param {number} n* return {number}*/
var fib function(n) {const dp new Array(n 1);dp[0] 0;dp[1] 1;for (let i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];
};
分析时间复杂度为 O(n)空间复杂度为 O(n)。
题解2动态规划优化
思路可以看到 dp[i] 依赖于前2个状态用2个变量记录前2个数在循环中直接更新这2个变量。
/*** param {number} n* return {number}*/
var fib function(n) {if (n 0) {return 0;}if (n 2) {return 1;}let a 1, b 1;while (n-- 2) {const c a b;a b;b c;}return b;
};
分析时间复杂度为 O(n)空间复杂度为 O(1)。
收获
动态规划5步曲
dp 数组以及下标的含义。递推公式。dp 数组初始化。遍历顺序。打印 dp 数组。
