1. 斐波那契数（LeetCode-509）
题目
斐波那契数 （通常用 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
提示：
0 <= n <= 30
思路
这题很简单，我试着用五部曲练练手
dp[i] 的意义为：第 i 个数的斐波那契数值为 dp[i]
d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ]
dp[0]=0 dp[1]=1
根据递推公式可知，dp[i] 依赖它的前两个元素，所以一定是从前往后遍历
推导一下前十项 0 1 1 2 3 5 8 13 21 34 55
代码展示
class Solution { public: int fib(int n) { vector<int> dp(35); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } };
但其实还可以优化，因为dp[i] 只依赖它的前两个元素，只需维护两个元素，没有必要写出整个数组，浪费了空间
class Solution { public: int fib(int n) { vector<int> dp(3); dp[0] = 0; dp[1] = 1; if (n < 2) { return dp[n]; } int result; for (int i = 2; i <= n; i++) { result = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = result; } return result; } };
