10.1 斐波那契數(shù)列

題目鏈接

?？途W(wǎng)

題目描述

求斐波那契數(shù)列的第 n 項(xiàng)，n <= 39。

解題思路

如果使用遞歸求解，會(huì)重復(fù)計(jì)算一些子問(wèn)題。例如，計(jì)算 f(4) 需要計(jì)算 f(3) 和 f(2)，計(jì)算 f(3) 需要計(jì)算 f(2) 和 f(1)，可以看到 f(2) 被重復(fù)計(jì)算了。

遞歸是將一個(gè)問(wèn)題劃分成多個(gè)子問(wèn)題求解，動(dòng)態(tài)規(guī)劃也是如此，但是動(dòng)態(tài)規(guī)劃會(huì)把子問(wèn)題的解緩存起來(lái)，從而避免重復(fù)求解子問(wèn)題。

public int Fibonacci(int n) {if (n <= 1)return n;int[] fib = new int[n + 1];fib[1] = 1;for (int i = 2; i <= n; i++)fib[i] = fib[i - 1] + fib[i - 2];return fib[n];
}

考慮到第 i 項(xiàng)只與第 i-1 和第 i-2 項(xiàng)有關(guān)，因此只需要存儲(chǔ)前兩項(xiàng)的值就能求解第 i 項(xiàng)，從而將空間復(fù)雜度由 O(N) 降低為 O(1)。

public int Fibonacci(int n) {if (n <= 1)return n;int pre2 = 0, pre1 = 1;int fib = 0;for (int i = 2; i <= n; i++) {fib = pre2 + pre1;pre2 = pre1;pre1 = fib;}return fib;
}

由于待求解的 n 小于 40，因此可以將前 40 項(xiàng)的結(jié)果先進(jìn)行計(jì)算，之后就能以 O(1) 時(shí)間復(fù)雜度得到第 n 項(xiàng)的值。

public class Solution {private int[] fib = new int[40];public Solution() {fib[1] = 1;for (int i = 2; i < fib.length; i++)fib[i] = fib[i - 1] + fib[i - 2];}public int Fibonacci(int n) {return fib[n];}
}

結(jié)尾

原文鏈接