LintCode 366: Fibnacci
程序员文章站
2022-07-05 12:59:04
...
这题虽然简单,但是也容易错。
下面给出迭代的两种解法。
迭代解法1:我的版本
class Solution {
public:
/**
* @param n: an integer
* @return: an ineger f(n)
*/
int fibonacci(int n) {
if (n == 1) return 0;
if (n == 2) return 1;
int a1 = 0;
int a2 = 1;
for (int i = 3; i <= n; ++i) {
int temp = a2;
a2 += a1;
a1 = temp;
}
return a2;
}
};
迭代解法2:九章版本
class Solution{
public:
int fibonacci(int n) {
int a, b;
a = 0;
b = 1;
for(int i = 1; i < n; i++) {
int c = a + b;
a = b;
b = c;
}
return a;
}
};
这题也可以用递归+记忆化搜索做。
TBD。
上一篇: Windows创建进程