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：
- 输入：2
- 输出：1
- 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
- 输入：3
- 输出：2
- 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
- 输入：4
- 输出：3
- 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
- 0 <= n <= 30
解题思路：
之前刷过一边代码随想录，现在再次回归算法，不过这次是选从最后往前刷，这道题目是动态规划类型的题目，属于简单题目，那么我们应该如果做动态规划类型的题目呢？
一般动态规划都需要dp这个数组，该类题目重点要理解dp[]数组中存的元素的含义，否则将会很迷
我们来看这道题目：
首先题目给了**“该数列由 0 和 1 开始”**，看到这里我们就要想到初始化两个默认值，并且需要考虑F(0)和F(1)的特殊情况。接着我们需要准备dp数组，dp数组的大小如何确定呢？为什么是n+1，而不是n呢？我们下面解答。
- 确定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[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
- 举例推导dp数组
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
0 1 1 2 3 5 8 13 21 34 55
如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。
以上我们用动规的方法分析完了
代码实现：
/**
* 509. 斐波那契数
*
*/
public class FibonacciNumbers {
public int fib(int n) {
if(n < 2){
return n;
}
int[] dp = new int[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];
}
}
最后我们解释一下上面的问题，dp数组的大小如何确定呢？为什么是n+1，而不是n呢？
在这个实现中，数组的索引表示斐波那契数的位置，数组的值存储相应位置的斐波那契数。由于数组的索引从0开始，所以需要一个长度为n+1的数组，以便能够存储从第0个到第n个斐波那契数，共计n+1个数。
例如，当n=5时，需要一个长度为6的数组来存储从第0个到第5个斐波那契数，即dp[0]，dp[1]，dp[2]，dp[3]，dp[4]，dp[5]。
因此，初始化int数组为n+1的目的是为了确保数组的长度足够存储从第0个到第n个斐波那契数。
评论区