机考刷题之 3 LeetCode 509 斐波那契数列
题目
分析
最经典的递归题目,f(n) = f(n-1)+f(n-2);
其中边界条件,f(0)=0,f(1)=1。
注意在n>1时,循环次数为n-2,因为f(0)和f(1)在第一次判定n时返回。
代码
class Solution { public: int fib(int n) { if(n<=1){ return n; } int a=0,b=1,c=0; while(n-->=2){ c=a+b; a=b; b=c; } return c; } };