Leetcode#509:

题目描述

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。

题解 python3

class Solution:
    def fib(self, n: int) -> int:
        #动态规划 O(n)空间复杂度
        res = [0,1]
        for i in range(2, n+1):
            res.append(res[i-1] + res[i-2])
        return res[n]

        #动态规划O(1)空间复杂度
        # if n <= 1:
        #     return n
        # n1 = 0
        # n2 = 1
        # for i in range(0, n-1):
        # #注意下面是同时赋值
        #     n1, n2 = n2, n1+n2
        # return n2