LeetCode刷题笔记第509题：斐波那契数

LeetCode刷题笔记第509题：斐波那契数

想法一：
递归
斐波那契数除了第一个和第二个数为1，其余所有数均为其前两个数之和，通过递归获得相对输入的斐波那契数。时间复杂度：O(2^n)，空间复杂度：O(n)。

class Solution: def fib(self, n: int) -> int: if n == 0: return 0 elif n == 1 or n == 2: return 1 else: return self.fib(n-1) + self.fib(n-2)

想法二：
动态规划
在动态规划中要注意三点：

最优子结构。边界状态转移公式
参照以上三点构建动态规划方法
LeetCode中斐波那契数从0开始，其边界也是从0开始，之后n等于1或n等于2的值为1。斐波那契数的最优子结构是其前两个数相加。状态转移方程为前两个和为第三个的值。时间复杂度：O(n)，空间复杂度：O(1)。

class Solution: def fib(self, n: int) -> int: if n < 2: return n p = 0 q = 1 r = 1 while r < n: p, q = q, p + q r += 1 return q