题解 | #斐波那契数列#
斐波那契数列
https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3
class Solution {
public:
// 注意要求空间复杂度是O(1) 所以不能用vector来做了
// 先试试dp
int Fibonacci(int n) {
if(n<3)
return 1;
int dp1 = 1;
int dp2 = 1;
int tmp = 0;
for(int i=3; i<=n; ++i)
{
tmp = dp1 + dp2; // 递推
dp1 = dp2;
dp2 = tmp;
}
return tmp;
}
};
自己：不借用数组 因为转移公式里之和两项有关 时间复杂度O(n)
投递猿辅导等公司6个岗位 >