fibonacci数列

我记得毕业那年，面试百度，最后一面面试官让我写求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();
}

爬楼梯问题和斐波那契数列递推公式相同，但初始项并不相同。