-
f(1) = 1。
-
f(2) = 1。
-
f(3) = f(2) + f(1) = 2。
-
f(4) = f(3) + f(2) = 3。
-
f(5) = f(4) + f(3) = 5。
-
f(n) = f(n-2) + f(n-1)
//cpp
class Solution {
public:
int Fibonacci(int n) {
if(n == 0) return 0;
if(n <= 2) return 1;
int a = 1, b = 1, c = 0;//a保存f(n-2),b保存f(n-1),c保存f(n)
for(int i = 3; i <= n; ++i)//递推求出f(i)
{
c = (a + b) ;//f(n) = f(n - 1) + f(n - 2)
a = b;//a保存b
b = c;//b保存c
}
return c;
}
};
如果就觉得不错,欢迎点赞、收藏、评论
可以可以!
为什么面试千万别用递归啊,大佬求指教
消耗开销大
明白了蟹蟹蟹蟹!
递归会重复计算好多值
那用啥方法呀?
迭代