最后更新于3年前
易得状态转移方程（其实严格来说不算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
