兔子繁殖問題：
這是一個有趣的古典數學問題，著名意大利數學家Fibonacci曾提出一個問題：有一對小兔子，從出生后第3個月起每個月都生一對兔子。小兔子長到第3個月后每個月又生一對兔子。按此規律，假設沒有兔子死亡，第一個月有一對剛出生的小兔子，問第n個月有多少對兔子？

相信上面的題目稍微有點經驗的程序員都了解過，這就是著名的斐波那契數列（Fibonacci sequence），該數列，又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……
特點：這個數列從第3項開始，每一項都等于前兩項之和。

表達式：F[n]=F[n-1]+F[n-2] (n>=2,F[0]=0,F[1]=1)

看到這個表達式相信大多數讀者都能想到使用遞歸算法實現，那么由此我們可以得到求解斐波那契數列的一種算法：

public class Main {public static int f (int n) {if (n <= 2) {return 1;} else {return f(n-1) + f(n-2);}}public static void main(String[] args) {int n = 12;System.out.println(f(n));} }

注：若用于求解兔子繁殖問題需要對輸入參數進行額外處理

但是！！！
對于小數據來說，上面的算法或許還可行，但是我們發現用30作為輸入進行計算的時候，程序輸出結果時已經有了一定的時間延遲，而用再大的數據來測試就會發現結果在短時間內根本出不來，這是為什么呢？
對于上面的遞歸求解方法來說，時間復雜度為O(2^n)，所以效率非常慢，為了計算一個f(n)，需要存在一個f(n-1)和一個f(n-2)，然而f(n-1)遞歸地對f(n-2)h和f(n-3)進行調用，因此存在兩個單獨計算f(n-2)的調用。繼續跟蹤整個算法會發現，f(n-3)被計算了3次，f(n-4)被計算了5次，而f(n-5)則是8次。冗余的計算無疑加重了編譯器的負擔，如果編譯器不能對之前計算過的數據進行保留，這樣的增長就無法比避免。
所以這里給出第二種算法,時間復雜度為O(n)

public class Main {public static int f (int n) {if (n <= 2) {return 1;}int last = 1;int nextToLast = 1;int answer = 1;//前2位都為1for (int i = 3; i <= n; i++) {answer = last + nextToLast;nextToLast = last;last = answer;}return answer;}public static void main(String[] args) {int n = 12;System.out.println(f(n));} }

第二種算法即使用非常大的數據進行測試也僅僅是稍有延遲，短時間內基本可以輸出。

下面我們來分析一下這兩種算法的思想

分治策略是對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。
提到分治策略就不得不提遞歸，遞歸與分治的關系網上說的有諸多含糊不清，愚見，分治是一種思想，而遞歸是實現分治思想的方法。

動態規劃的基本思想與分治策略類似，區別就在于動態規劃是一種帶基于記憶化搜素的思想，這也是不同于普通搜索算法的一大特點。
所以，動態規劃思想常用于解決問題中含有較多重疊子的問題，這種問題應盡量避免使用單純的遞歸算法實現。

總結

以上是生活随笔為你收集整理的斐波那契数列（一）--对比递归与动态规划（JAVA）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。