509.斐波那契数
目录
1 题目描述
2 解题思路
$a_n = a_{n-1} + a_{n-2}$，利用这一递推关系构建for循环即可，实际上只需要容量为2的数组。
3 代码
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];
}
};