0509. 斐波那契数

0509. 斐波那契数 #

  • 标签:数组
  • 难度:简单

题目大意 #

描述:给定一个整数 n

要求:计算第 n 个斐波那契数。

说明

  • 斐波那契数列的定义如下:
    • f(0) = 0, f(1) = 1
    • f(n) = f(n - 1) + f(n - 2),其中 n > 1

示例

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

解题思路 #

思路 1:递归算法 #

根据我们的递推三步走策略,写出对应的递归代码。

  1. 写出递推公式:f(n) = f(n - 1) + f(n - 2)
  2. 明确终止条件:f(0) = 0, f(1) = 1
  3. 翻译为递归代码:
    1. 定义递归函数:fib(self, n) 表示输入参数为问题的规模 n,返回结果为第 n 个斐波那契数。
    2. 书写递归主体:return self.fib(n - 1) + self.fib(n - 2)
    3. 明确递归终止条件:
      1. if n == 0: return 0
      2. if n == 1: return 1

思路 1:代码 #

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

思路 2:递推算法 #

根据斐波那契的递推公式 f(n) = f(n - 1) + f(n - 2),我们可以直接写出对应的递推算法。

思路 2:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        
        f1, f2, f3 = 0, 0, 1
        for i in range(2, n+1):
            f1, f2 = f2, f3
            f3 = f1 + f2
        return f3
本站总访问量  次  |  您是本站第  位访问者