我記得畢業(yè)那年，面試百度，最后一面面試官讓我寫求fibonacci數(shù)列的第n項(xiàng)的值。
當(dāng)時(shí)有些意外，沒想到會(huì)讓寫這么簡單的題目。
一開始我用記憶化遞歸實(shí)現(xiàn)，這種算法需要記錄中間的計(jì)算結(jié)果（避免重復(fù)運(yùn)算），但當(dāng)n很大時(shí)有StackOverFlow的風(fēng)險(xiǎn)。
后來用遞推實(shí)現(xiàn)，這種算法避免了溢出問題，但還是記錄了中間計(jì)算結(jié)果。
我繼續(xù)優(yōu)化：

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;
}

很長時(shí)間，我都以為這是最佳版本了，其實(shí)至少還有兩個(gè)更牛的算法。
通項(xiàng)公式：算法復(fù)雜度是O(1)，但公式中有無理數(shù)，所以會(huì)有精度損失。
分而治之：請(qǐng)參考《編程之美》2.9

很多問題內(nèi)部的原理就是fabonacci數(shù)列，比如爬樓梯的問題。
問題看起來完了?？墒?strong>任何問題都不是孤島，一定可以延伸到一個(gè)深度。比如爬樓梯問題，一個(gè)擴(kuò)展問題是打印每種可行解。
這個(gè)問題本質(zhì)上是一個(gè)無限背包問題，每次最多有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();  // 經(jīng)典錯(cuò)誤：沒有push，怎么來的pop？
        cnt++;
        return;
    }
    stack.push(1);
    stairs(n - 1, stack);
    stack.pop();

    stack.push(2);
    stairs(n - 2, stack);
    stack.pop();
}

爬樓梯問題和斐波那契數(shù)列遞推公式相同，但初始項(xiàng)并不相同。