509. 斐波那契数 - 已题解语言：C#/Python/C++/Java/JavaScript/Go/Ruby

LeetCode Python, Java, C++ > 动态规划 > 509. 斐波那契数 > 已支持 C#, Python, C++, Java, JavaScript, Go, Ruby > LeetCode GitHub Code 或转发

力扣链接：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

思路
上一题 下一题

“递归”的模式

递归（Recursion）是计算机科学和数学中的一个重要概念，指的是一个函数在其定义中 直接或间接调用自身 的方法。

递归的核心思想

自我调用：函数在执行过程中调用自身。
终止条件：递归必须有一个终止条件，防止无限循环。
递归方程：通过方程，问题逐步向“终止条件”靠近。

复杂度

时间复杂度

O(N)

空间复杂度

O(N)

解释

如果不加用于缓存已知结果的Map，时间复杂度将上升为O( 2^N )

C# #

public class Solution {
    IDictionary<int, int> numToFibNum = new Dictionary<int, int>();

    public int Fib(int n) {
        if (n <= 1) {
            return n;
        }

        if (numToFibNum.ContainsKey(n)) {
            return numToFibNum[n];
        }

        numToFibNum[n] = Fib(n - 1) + Fib(n - 2);

        return numToFibNum[n];
    }
}

Python #

class Solution:
    @cache
    def fib(self, n: int) -> int:
        if n <= 1:
            return n

        return self.fib(n - 1) + self.fib(n - 2)

C++ #

class Solution {
public:
    int fib(int n) {
        if (n <= 1) {
            return n;
        }

        if (num_to_fib_num_.contains(n)) {
            return num_to_fib_num_[n];
        }

        num_to_fib_num_[n] = fib(n - 1) + fib(n - 2);

        return num_to_fib_num_[n];
    }

private:
    unordered_map<int, int> num_to_fib_num_;
};

Java #

class Solution {
    var numToFibNum = new HashMap<Integer, Integer>();

    public int fib(int n) {
        if (n <= 1) {
            return n;
        }

        if (numToFibNum.containsKey(n)) {
            return numToFibNum.get(n);
        }

        numToFibNum.put(n, fib(n - 1) + fib(n - 2));

        return numToFibNum.get(n);
    }
}

JavaScript #

const numToFibNum = new Map()

var fib = function (n) {
    if (n <= 1) {
        return n
    }

    if (numToFibNum.has(n)) {
        return numToFibNum.get(n)
    }

    numToFibNum.set(n, fib(n - 1) + fib(n - 2))

    return numToFibNum.get(n)
};

Go #

func fib(m int) int {
    numToFibNum := map[int]int{}

    var fibonacci func (int) int

    fibonacci = func (n int) int {
        if n <= 1 {
            return n
        }

        if result, ok := numToFibNum[n]; ok {
            return result
        }

        numToFibNum[n] = fibonacci(n - 1) + fibonacci(n - 2)
        return numToFibNum[n]
    }

    return fibonacci(m)
}

Ruby #

def fib(n)
  return n if n <= 1

  @cache = {} if @cache.nil?

  return @cache[n] if @cache.key?(n)

  @cache[n] = fib(n - 1) + fib(n - 2)

  @cache[n]
end

其它语言

欢迎贡献代码到 LeetCode Python GitHub -> 509. 斐波那契数。感谢！

题解2的思路：动态规划

“动态规划”的模式

“动态规划”，需要用dp数组来保存结果。dp[i][j]的值可以由它的前一个（或多个）值通过公式转化出来。因此，dp[i][j]值是一步一步推导出来的，它和先前的dp记录值都有联系。

“动态规划”分为五步

确定数组dp的每个值代表的含义。
初始化数组dp的值。
根据一个示例，按顺序填入dp网格数据。
根据dp网格数据，推导出递推公式。
写出程序，并打印dp数组，不合预期就调整。

细说这五步

确定数组dp的每个值代表的含义。
- 先确定dp是一维数组还是二维数组。“一维滚动数组”意味着每次迭代时都会覆盖数组的值。大多时候，用“一维滚动数组”代替“二维数组”可以简化代码；但有些题目，比如要操作“两个位置可互换的数组”，为了理解方便，还是使用“二维数组”。
- 尝试使用问题所求的返回值的含义作为 dp[i]（一维）或dp[i][j]（二维）的含义，约60%的概率能行。如果不行，再尝试其他含义。
- 设计上尽量考虑保存更丰富的信息，重复信息只在某个dp[i]中保存一次就够了。
- 使用简化的含义。如果用布尔值可以解决问题，就不要用数值。
初始化数组dp的值。dp的值涉及两个层面：
1. dp的长度。通常是：条件数组长度加1或条件数组长度。
2. dp[i]或dp[i][j]的值。dp[0]或dp[0][0]有时需要特殊处理。
根据一个示例，按顺序填入dp网格数据。
- “递推公式”是“动态规划”算法的核心。但“递推公式”是隐晦的，想得到它，就需要制表，用数据启发自己。
- 如果原示例不够好，需要自己重新设计一个。
- 根据示例，填入dp网格数据，需要“按顺序”填，这是很重要的，因为它决定了代码的遍历顺序。
- 大多时候，从左到右，从上到下。但有时需要从右向左、由下而上、从中间向右（或左），如“回文串”问题。有时，还需要一行遍历两次，先正向，再反向。
- 当顺序决定对了，起点就决定好了，从起点出发，“按顺序”填写dp网格数据，这也是在模拟程序处理的过程。
- 在此过程中，您将获得写出“递推公式”的灵感。如果您已经能推导出公式，不需要填完网格。
根据dp网格数据，推导出递推公式。
- 有三个特别的位置需要注意： dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]，当前的 dp[i][j]往往取决于它们。
- 操作“两个位置可互换的数组”时，因为对称性，我们可能需要同时使用dp[i - 1][j]和dp[i][j - 1]。
写出程序，并打印dp数组，不合预期就调整。
- 重点分析那些不合预期的数值。

读完了上面的内容，是不是感觉“动态规划”也没有那么难了？试着解出这道题吧。🤗

复杂度

时间复杂度

O(N)

空间复杂度

O(N)

C# #

public class Solution
{
    public int Fib(int n)
    {
        if (n <= 1)
            return n;

        var dp = new int[n + 1];
        dp[1] = 1;

        for (var i = 2; i < dp.Length; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

Python #

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0

        dp = [0] * (n + 1)
        dp[1] = 1

        for i in range(2, len(dp)):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[-1]

C++ #

class Solution {
public:
    int fib(int n) {
        if (n <= 1) {
            return n;
        }

        auto dp = vector<int>(n + 1);
        dp[1] = 1;

        for (auto i = 2; i < dp.size(); i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
};

Java #

class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }

        var dp = new int[n + 1];
        dp[1] = 1;

        for (var i = 2; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

JavaScript #

var fib = function (n) {
    if (n <= 1) {
        return n
    }

    const dp = Array(n + 1).fill(0)
    dp[1] = 1

    for (let i = 2; i < dp.length; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }

    return dp[n]
};

Go #

func fib(n int) int {
    if n == 0 {
        return 0
    }

    dp := make([]int, n + 1)
    dp[1] = 1

    for i := 2; i <= n; i++ {
        dp[i] = dp[i - 2] + dp[i - 1]
    }

    return dp[n]
}

Ruby #

def fib(n)
  return 0 if n == 0

  dp = Array.new(n + 1, 0)
  dp[1] = 1

  (2...dp.size).each do |i|
    dp[i] = dp[i - 1] + dp[i - 2]
  end

  dp[-1]
end

其它语言

欢迎贡献代码到 LeetCode Python GitHub -> 509. 斐波那契数。感谢！

题解3的思路：动态规划（滚动变量）

“动态规划”的模式

“动态规划”分为五步

确定数组dp的每个值代表的含义。
初始化数组dp的值。
根据一个示例，按顺序填入dp网格数据。
根据dp网格数据，推导出递推公式。
写出程序，并打印dp数组，不合预期就调整。

细说这五步

确定数组dp的每个值代表的含义。
- 先确定dp是一维数组还是二维数组。“一维滚动数组”意味着每次迭代时都会覆盖数组的值。大多时候，用“一维滚动数组”代替“二维数组”可以简化代码；但有些题目，比如要操作“两个位置可互换的数组”，为了理解方便，还是使用“二维数组”。
- 尝试使用问题所求的返回值的含义作为 dp[i]（一维）或dp[i][j]（二维）的含义，约60%的概率能行。如果不行，再尝试其他含义。
- 设计上尽量考虑保存更丰富的信息，重复信息只在某个dp[i]中保存一次就够了。
- 使用简化的含义。如果用布尔值可以解决问题，就不要用数值。
初始化数组dp的值。dp的值涉及两个层面：
1. dp的长度。通常是：条件数组长度加1或条件数组长度。
2. dp[i]或dp[i][j]的值。dp[0]或dp[0][0]有时需要特殊处理。
根据一个示例，按顺序填入dp网格数据。
- “递推公式”是“动态规划”算法的核心。但“递推公式”是隐晦的，想得到它，就需要制表，用数据启发自己。
- 如果原示例不够好，需要自己重新设计一个。
- 根据示例，填入dp网格数据，需要“按顺序”填，这是很重要的，因为它决定了代码的遍历顺序。
- 大多时候，从左到右，从上到下。但有时需要从右向左、由下而上、从中间向右（或左），如“回文串”问题。有时，还需要一行遍历两次，先正向，再反向。
- 当顺序决定对了，起点就决定好了，从起点出发，“按顺序”填写dp网格数据，这也是在模拟程序处理的过程。
- 在此过程中，您将获得写出“递推公式”的灵感。如果您已经能推导出公式，不需要填完网格。
根据dp网格数据，推导出递推公式。
- 有三个特别的位置需要注意： dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]，当前的 dp[i][j]往往取决于它们。
- 操作“两个位置可互换的数组”时，因为对称性，我们可能需要同时使用dp[i - 1][j]和dp[i][j - 1]。
写出程序，并打印dp数组，不合预期就调整。
- 重点分析那些不合预期的数值。

读完了上面的内容，是不是感觉“动态规划”也没有那么难了？试着解出这道题吧。🤗

复杂度

时间复杂度

O(N)

空间复杂度

O(1)

C# #

public class Solution
{
    public int Fib(int n)
    {
        if (n <= 1)
            return n;

        int[] dp = [0, 1];

        for (var i = 2; i <= n; i++)
        {
            var dc = (int[])dp.Clone();

            dp[0] = dc[1];
            dp[1] = dc[0] + dc[1];
        }

        return dp[1];
    }
}

Python #

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0

        dp = [0, 1]

        for i in range(2, n + 1):
            dc = dp.copy()

            dp[0] = dc[1]
            dp[1] = dc[0] + dc[1]

        return dp[1]

C++ #

class Solution {
public:
    int fib(int n) {
        if (n <= 1) {
            return n;
        }

        vector dp = {0, 1};

        for (auto i = 2; i <= n; i++) {
            auto dc = dp;

            dp[0] = dc[1];
            dp[1] = dc[0] + dc[1];
        }

        return dp[1];
    }
};

Java #

class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }

        int[] dp = {0, 1};

        for (var i = 2; i <= n; i++) {
            var dc = dp.clone();

            dp[0] = dc[1];
            dp[1] = dc[0] + dc[1];
        }

        return dp[1];
    }
}

JavaScript #

var fib = function (n) {
    if (n <= 1) {
        return n
    }

    const dp = [0, 1]

    for (let i = 2; i <= n; i++) {
        const dc = [...dp]

        dp[0] = dc[1]
        dp[1] = dc[0] + dc[1]
    }

    return dp[1]
};

Go #

func fib(n int) int {
    if n == 0 {
        return 0
    }

    dp := []int{0, 1}

    for i := 2; i <= n; i++ {
        dc := slices.Clone(dp)

        dp[0] = dc[1]
        dp[1] = dc[0] + dc[1]
    }

    return dp[1]
}

Ruby #

def fib(n)
  return 0 if n == 0

  dp = [0, 1]

  (2..n).each do |i|
    dc = dp.clone

    dp[0] = dc[1]
    dp[1] = dc[0] + dc[1]
  end

  dp[1]
end

其它语言

欢迎贡献代码到 LeetCode Python GitHub -> 509. 斐波那契数。感谢！

上一题下一题

游客

全部题解

Welcome !

LeetCode Python, Java, C++ > 动态规划 > 509. 斐波那契数 > 已支持 C#, Python, C++, Java, JavaScript, Go, Ruby > LeetCode GitHub Code 或 转发

示例 1:

示例 2:

示例 3:

约束:

思路 上一题下一题

“递归”的模式

递归的核心思想

复杂度

时间复杂度

空间复杂度

解释

C# #

Python #

C++ #

Java #

JavaScript #

Go #

Ruby #

其它语言

题解2的思路：动态规划

“动态规划”的模式

“动态规划”分为五步

细说这五步

复杂度

时间复杂度

空间复杂度

C# #

Python #

C++ #

Java #

JavaScript #

Go #

Ruby #

其它语言

题解3的思路：动态规划（滚动变量）

“动态规划”的模式

“动态规划”分为五步

细说这五步

复杂度

时间复杂度

空间复杂度

C# #

Python #

C++ #

Java #

JavaScript #

Go #

Ruby #

其它语言

LeetCode Python, Java, C++ > 动态规划 > 509. 斐波那契数 > 已支持 C#, Python, C++, Java, JavaScript, Go, Ruby > LeetCode GitHub Code 或转发

思路
上一题下一题