leetcode 509 斐波那契数

今天重新看了下动态规划， 它和递归的区别就是，它是自下而上的。 还了解到状态压缩

如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据 于是就刷了这道简答题,用到了状态压缩

class Solution:
    def fib(self, n: int) -> int:
            if n == 0:
                return 0
            if n == 1 or n == 2:
                return 1
            prev = 1
            curr = 1
            for i in range(3, n + 1):
                sum = prev + curr
                prev = curr
                curr = sum
            return sum