我記得畢業(yè)那年铆隘，面試百度卓舵，最后一面面試官讓我寫求fibonacci數(shù)列的第n項(xiàng)的值。
當(dāng)時(shí)有些意外膀钠，沒想到會讓寫這么簡單的題目边器。
一開始我用記憶化遞歸實(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ù)兴泥，所以會有精度損失工育。
分而治之：請參考《編程之美》2.9
很多問題內(nèi)部的原理就是fabonacci數(shù)列，比如爬樓梯的問題搓彻。
問題看起來完了如绸≈鲂啵可是任何問題都不是孤島，一定可以延伸到一個(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)并不相同提佣。
