509. 斐波那契数
LeetCode题目要求
斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定 n ,请计算 F(n) 。
示例
输入:n = 2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1
输入:n = 3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2
解题思路
要用一个一维 dp 数组来保存递归的结果
五部曲
- 确定dp数组以及下标的含义 dp[i]的定义为:第i个数的斐波那契数值是dp[i]
- 确定递推公式:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
- dp数组如何初始化:dp[0] = 0; dp[1] = 1;
- 确定遍历顺序:dp[i] 依赖 dp[i - 1] 和 dp[i - 2],遍历顺序是从前到后遍历的
- 举例推导dp数组:当N为10的时候,dp数组应该是如下的数列:0 1 1 2 3 5 8 13 21 34 55
上代码
class Solution {
public int fib(int n) {
if (n <= 1) {
return n;
}
// 1 确定数组 dp
int[] dp = new int[n+1];
// 3 dp 初始化
dp[0] = 0;
dp[1] = 1;
// 4 遍历顺序
for (int i = 2; i <= n; i++) {
// 2 递推公式
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
精简版
class Solution {
public int fib(int n) {
if (n < 2) return n;
int a = 0, b = 1, c = 0;
for (int i = 1; i < n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
重难点
理解五部曲
附:学习资料链接
标签:契数,38,int,斐波,数组,509,dp From: https://www.cnblogs.com/blacksonny/p/17156336.html