我记得毕业那年，面试百度，最后一面面试官让我写求fibonacci数列的第n项的值。
当时有些意外，没想到会让写这么简单的题目。
一开始我用记忆化递归实现，这种算法需要记录中间的计算结果（避免重复运算），但当n很大时有StackOverFlow的风险。
后来用递推实现，这种算法避免了溢出问题，但还是记录了中间计算结果。
我继续优化：
int fibonacci(final int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int a = 1;
int b = 1;
int x = 0;
for (int i = 3; i <= n; i++) {
x = a + b;
a = b;
b = x;
}
return x;
}
很长时间，我都以为这是最佳版本了，其实至少还有两个更牛的算法。
通项公式：算法复杂度是O(1)，但公式中有无理数，所以会有精度损失。
分而治之：请参考《编程之美》2.9
很多问题内部的原理就是fabonacci数列，比如爬楼梯的问题。
问题看起来完了。可是任何问题都不是孤岛，一定可以延伸到一个深度。比如爬楼梯问题，一个扩展问题是打印每种可行解。
这个问题本质上是一个无限背包问题，每次最多有2中选择。
public void print(Stack<Integer> stack, int n) {
if (n == 0) {
cnt++;
System.out.println(stack);
}
if (n >= 2) {
stack.push(2);
print(stack, n - 2);
stack.pop();
}
if (n >= 1) {
stack.push(1);
print(stack, n - 1);
stack.pop();
}
}
下面这段代码也是OK的
private Stack<Integer> stack = new Stack<>();
public void print(int n) {
if (n == 0) {
cnt++;
System.out.println(stack);
}
if (n >= 2) {
stack.push(2);
print(n - 2);
stack.pop();
}
if (n >= 1) {
stack.push(1);
print(n - 1);
stack.pop();
}
}
2020-02-21
void stairs(int n, Stack<Integer> stack) {
if (n < 0) {
return;
}
if (n == 0) {
System.out.println(stack);
stack.pop(); // 经典错误：没有push，怎么来的pop？
cnt++;
return;
}
stack.push(1);
stairs(n - 1, stack);
stack.pop();
stack.push(2);
stairs(n - 2, stack);
stack.pop();
}
爬楼梯问题和斐波那契数列递推公式相同，但初始项并不相同。
