题目描述 链接到标题
解题思路 链接到标题
$a_n = a_{n-1} + a_{n-2}$，利用这一递推关系构建for循环即可，实际上只需要容量为2的数组。
代码 链接到标题
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
int dp[2];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
};