A·Y

LeetCode 509 - 斐波那契数

8/12/2021 LeetCode
简单

原题链接：https://leetcode-cn.com/problems/fibonacci-number/ (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

# Python题解

# 个人题解：递归

class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """
        def getfn(n):
            if n == 0 or n == 1:
                return n
            else:
                return getfn(n - 1) + getfn(n - 2)

        return getfn(n)
1
2
3
4
5
6
7
8
9
10
11
12
13

# 官方题解：动态规划

class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 2:
            return n
        p, q, r = 0, 0, 1
        for _ in range(1, n):  # 官方是这样的 for i in range(2, n+1)
            p, q = q, r
            r = p + q
        return r
1
2
3
4
5
6
7
8
9
10
11
12
13

# 总结

经典递归，没啥说的。

动态规划，时间复杂度：O(n)，空间复杂度：O(1)，不错的思路。

其实官方还有矩阵快速幂与通项公式的解，感兴趣可以自行了解下。斐波那契数官方题解 (opens new window)