LeetCode 509 - 斐波那契数

Algorithm LeetCode
August 13, 2021
简单
原题链接：https://leetcode-cn.com/problems/fibonacci-number/

题目描述

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

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)python

官方题解：动态规划

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 rpython

总结

经典递归，没啥说的。
动态规划，时间复杂度：O(n)，空间复杂度：O(1)，不错的思路。
其实官方还有矩阵快速幂与通项公式的解，感兴趣可以自行了解下。斐波那契数官方题解
The End