509.斐波那契数

https://leetcode-cn.com/problems/fibonacci-number/

解法一：dp

易得状态转移方程（其实严格来说不算dp，因为没有求最值）

dp[n] = dp[n-1] + dp[n-2]

初始条件

dp[0] = 0, dp[1] = 1

由于只需从前往后推出dp[n]，最多只要记录前两位的状态，因此没必要创建长度为n的数组 改进：（状态压缩）i从2~n一次遍历，用p、q分别记录i-2、i-1位置的状态，每轮更新pq即可

class Solution:
    def fib(self, n: int) -> int:
        if n == 0 or n == 1:
            return n
        p = 0  #i-2位置
        q = 1  #i-1位置
        r = 0  #i位置
        for i in range(2, n+1):
            r = p + q
            p = q
            q = r
        return r