509 斐波那契数

本文最后更新于：2021年2月26日 下午

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N，计算 F(N)。

示例 1：

1
2
3
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2：

1
2
3
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3：

1
2
3
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

提示：

  • 0 ≤ N ≤ 30

Solution

思路参考：动态规划解题套路框架 、代码随想录

动态规划问题最困难的就是写出这个暴力解，即状态转移方程。只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# @lc code=start
class Solution:
    def fib(self, N: int) -> int:
        if N==0:
            return 0
        if N==1:
            return 1
        a, b = 0, 1
        for i in range(2, N+1):
            sum = a + b
            a = b
            b = sum
        return sum
# @lc code=end

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// @lc code=start
class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int dp[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];
    }
};
// @lc code=end

动规五部曲：

  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！