参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

# 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)手把手带你入门动态规划 | leetcode:509.斐波那契数 (opens new window),相信结合视频在看本篇题解,更有助于大家对本题的理解

# 思路

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

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

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

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

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

所以我总结的动规五部曲,是要用来贯穿整个动态规划系列的,就像之前讲过二叉树系列的递归三部曲 (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数组如何初始化

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

dp[0] = 0;
dp[1] = 1;
1
2
  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数组打印出来看看和我们推导的数列是不是一致的。

以上我们用动规的方法分析完了,C++代码如下:

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        vector<int> dp(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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

当然可以发现,我们只需要维护两个数值就可以了,不需要记录整个序列。

代码如下:

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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

# 递归解法

本题还可以使用递归解法来做

代码如下:

class Solution {
public:
    int fib(int N) {
        if (N < 2) return N;
        return fib(N - 1) + fib(N - 2);
    }
};
1
2
3
4
5
6
7
  • 时间复杂度:O(2^n)
  • 空间复杂度:O(n),算上了编程语言中实现递归的系统栈所占空间

这个递归的时间复杂度大家画一下树形图就知道了,如果不清晰的同学,可以看这篇:通过一道面试题目,讲一讲递归算法的时间复杂度! (opens new window)

# 总结

斐波那契数列这道题目是非常基础的题目,我在后面的动态规划的讲解中将会多次提到斐波那契数列!

这里我严格按照关于动态规划,你该了解这些! (opens new window)中的动规五部曲来分析了这道题目,一些分析步骤可能同学感觉没有必要搞的这么复杂,代码其实上来就可以撸出来。

但我还是强调一下,简单题是用来掌握方法论的,动规五部曲将在接下来的动态规划讲解中发挥重要作用,敬请期待!

就酱,循序渐进学算法,认准「代码随想录」!

# 其他语言版本

# Java

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
//非压缩状态的版本
class Solution {
    public int fib(int n) {
        if (n <= 1) return n;             
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int index = 2; index <= n; index++){
            dp[index] = dp[index - 1] + dp[index - 2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# Python

动态规划(版本一)


class Solution:
    def fib(self, n: int) -> int:
       
        # 排除 Corner Case
        if n == 0:
            return 0
        
        # 创建 dp table 
        dp = [0] * (n + 1)

        # 初始化 dp 数组
        dp[0] = 0
        dp[1] = 1

        # 遍历顺序: 由前向后。因为后面要用到前面的状态
        for i in range(2, n + 1):

            # 确定递归公式/状态转移公式
            dp[i] = dp[i - 1] + dp[i - 2]
        
        # 返回答案
        return dp[n]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

动态规划(版本二)


class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        dp = [0, 1]
        
        for i in range(2, n + 1):
            total = dp[0] + dp[1]
            dp[0] = dp[1]
            dp[1] = total
        
        return dp[1]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

动态规划(版本三)

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        prev1, prev2 = 0, 1
        
        for _ in range(2, n + 1):
            curr = prev1 + prev2
            prev1, prev2 = prev2, curr
        
        return prev2




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归(版本一)


class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        return self.fib(n - 1) + self.fib(n - 2)
1
2
3
4
5
6

# Go

func fib(n int) int {
    if n < 2 {
        return n
    }
    a, b, c := 0, 1, 0
    for i := 1; i < n; i++ {
        c = a + b
        a, b = b, c
    }
        return c
}
1
2
3
4
5
6
7
8
9
10
11

# Javascript

解法一

var fib = function(n) {
    let dp = [0, 1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    console.log(dp)
    return dp[n]
};
1
2
3
4
5
6
7
8

解法二:时间复杂度O(N),空间复杂度O(1)

var fib = function(n) {
    // 动规状态转移中,当前结果只依赖前两个元素的结果,所以只要两个变量代替dp数组记录状态过程。将空间复杂度降到O(1)
    let pre1 = 1
    let pre2 = 0
    let temp
    if (n === 0) return 0
    if (n === 1) return 1
    for(let i = 2; i <= n; i++) {
        temp = pre1
        pre1 = pre1 + pre2
        pre2 = temp
    }
    return pre1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# TypeScript

function fib(n: number): number {
    /**
        dp[i]: 第i个斐波那契数
        dp[0]: 0;
        dp[1]:1;
        ...
        dp[i] = dp[i - 1] + dp[i - 2];
     */
    const dp: number[] = [];
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# C

动态规划:

int fib(int n){
    //当n <= 1时,返回n
    if(n <= 1)
        return n;
    //动态开辟一个int数组,大小为n+1
    int *dp = (int *)malloc(sizeof(int) * (n + 1));
    //设置0号位为0,1号为为1
    dp[0] = 0;
    dp[1] = 1;

    //从前向后遍历数组(i=2; i <= n; ++i),下标为n时的元素为dp[i-1] + dp[i-2]
    int i;
    for(i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

递归实现:

int fib(int n){
    //若n小于等于1,返回n
    if(n <= 1)
        return n;
    //否则返回fib(n-1) + fib(n-2)
    return fib(n-1) + fib(n-2);
}
1
2
3
4
5
6
7

# Rust

动态规划:

impl Solution {
    pub fn fib(n: i32) -> i32 {
        if n <= 1 {
            return n;
        }
        let n = n as usize;
        let mut dp = vec![0; n + 1];
        dp[1] = 1;
        for i in 2..=n {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        dp[n]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

递归实现:

impl Solution {
    pub fn fib(n: i32) -> i32 {
        if n <= 1 {
            n
        } else {
            Self::fib(n - 1) + Self::fib(n - 2)
        }
    }
}
1
2
3
4
5
6
7
8
9

# Scala

动态规划:

object Solution {
  def fib(n: Int): Int = {
    if (n <= 1) return n
    var dp = new Array[Int](n + 1)
    dp(1) = 1
    for (i <- 2 to n) {
      dp(i) = dp(i - 1) + dp(i - 2)
    }
    dp(n)
  }
}
1
2
3
4
5
6
7
8
9
10
11

递归:

object Solution {
  def fib(n: Int): Int = {
    if (n <= 1) return n
    fib(n - 1) + fib(n - 2)
  }
}
1
2
3
4
5
6

# C#

动态规划:

public class Solution
{
    public int Fib(int n)
    {
        if(n<2) return n;
        int[] dp = new int[2] { 0, 1 };
        for (int i = 2; i <= n; i++)
        {
            int temp = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        return dp[1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

递归:

public class Solution
{
    public int Fib(int n)
    {
        if(n<2)
            return n;
        return Fib(n-1)+Fib(n-2);
    }
}
1
2
3
4
5
6
7
8
9

上次更新:: 9/19/2023, 4:22:40 PM
@2021-2022 代码随想录 版权所有 粤ICP备19156078号