509. 斐波那契数

力扣题目链接(opens new window)

斐波那契数，通常用 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

#思路

斐波那契数列大家应该非常熟悉不过了，非常适合作为动规第一道题目来练练手。

因为这道题目比较简单，可能一些同学并不需要做什么分析，直接顺手一写就过了。

但「代码随想录」的风格是：简单题目是用来加深对解题方法论的理解的。

通过这道题目让大家可以初步认识到，按照动规五部曲是如何解题的。

对于动规，如果没有方法论的话，可能简单题目可以顺手一写就过，难一点就不知道如何下手了。

所以我总结的动规五部曲，是要用来贯穿整个动态规划系列的，就像之前讲过二叉树系列的递归三部曲 (opens new window)，回溯法系列的回溯三部曲 (opens new window)一样。后面慢慢大家就会体会到，动规五部曲方法的重要性。

#动态规划

动规五部曲：

这里我们要用一个一维dp数组来保存递归的结果

  1. 确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

  1. 确定递推公式

为什么这是一道非常简单的入门题目呢？

因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

  1. dp数组如何初始化

题目中把如何初始化也直接给我们了，如下：

1
2
dp[0] = 0;
dp[1] = 1;
  1. 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

  1. 举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

Java代码如下：

递归打法

1
2
3
4
5
public int fib(int n) {
    if(n==1) return 0;
    if(n <= 2) return 1;
    return fib(n-1) + fib(n-2);
}

动态规划打法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 版本一
public int fib(int n) {
    // 首先知道dp的含义是什么？ 以及下标是什么意思
	int[] dp = new int[n];
    // 初始化
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2;i < n;i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n-1];
}
// 版本二
public int fib(int n) {
    int [] dp = new int[2];
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2;i < n;i++) {
        int sum = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = sum;
    }
    return dp[1];
}