斐波拉契數(shù)是一個很經(jīng)典的問題，也會很多公司面試的考題，每個學習計算機的同學都會接觸這個問題，尤其是在學習遞歸的時候，利用遞歸來解決斐波拉契數(shù)是很多教材采用的一個例子，所以很多同學一想到斐波拉契馬上就會采用遞歸，遞歸貌似簡單，但是效率真的很高嗎？不然！下面是我在學習動態(tài)規(guī)劃的過程中總結(jié)的集中解決斐波拉契數(shù)的不同方法：

一、最野蠻最原始的方法

[cpp]?view plaincopyprint?

long?f0(int?n)??

{??

????if?(n?==?0?||?n?==?1)??

????????return?n;??

????else??

????????return?F(n?-?1)?+?F(n?-?2);??

}??

這是最直接的遞歸方式，其時間復雜度為O(1.618^n)，是一個指數(shù)時間級的算法，當n超過30時，你就慢慢等待吧，運氣差的話直接死機了。

二、自底向上的動態(tài)規(guī)劃方法

我們已知F(0)和F(1)的值，則我們從F(2)開始就可以利用前面兩個已經(jīng)計算出來的值，這樣從小到大就可以最終求出F(n)

[cpp]?view plaincopyprint?

long?F(int?n)??

{??

????long?f1,f2,k,t;??

????if(n?<?2)?return?n;??

????f1?=?f2?=?1;??

????for?(k?=?2;?k?<?n;?k++)??

????{??

????<span?style="white-space:pre">??</span>t?=?f1?+?f2;??

????????f1?=?f2;??

????????f2?=?t;??

????}??

????return?t;??

}??

其時間復雜度已經(jīng)從指數(shù)級降到線性級O(n)了，空間復雜度為O(1)

三、自頂向下的動態(tài)規(guī)劃方法

這種方法也是采用遞歸的思想，但是確應用了動態(tài)規(guī)劃的原理：將以前的計算結(jié)果存儲起來備用，這樣在以后出現(xiàn)同樣的問題時就不用重復計算。也叫備忘錄方法。

[cpp]?view plaincopyprint?

int?fib[1000]?=?{0};??

long?f1(int?n)??

{??

????int?t;??

????if(fib[n]?!=?0)?return?fib[n];??

????if(n?==?0)?t?=?0;??

????if(n?==?1)?t?=?1;??

????if(n?>?1)?t?=?f1(n-1)?+?f1(n?-?2);??

????return?fib[n]?=?t;??

}??

自頂向下的動態(tài)規(guī)劃遞歸方法大大減少了遞歸調(diào)用的次數(shù)，避免了重復遞歸計算，其算法時間復雜度也為線性級，其關(guān)鍵就是能夠"保存已經(jīng)計算過的子問題的結(jié)果".

總結(jié)

以上是生活随笔為你收集整理的动态规划学习之三种方法解决斐波拉契数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。