Fibonacci DP

一句话理解

Fibonacci DP：f[i]=f[i-1]+f[i-2]。

为什么要学

线性 DP 第一例。

讲解

O(n) 时间和空间，可滚成 O(1) 空间。注意取模和 long long。

例子

f[1]=f[2]=1;
for(int i=3;i<=n;i++) f[i]=f[i-1]+f[i-2];

从小往大推。

常见错误

• 递归无记忆化算 f(40)。
• 溢出。