想寫一系列文章，總結(jié)一些題目，看看解決問題、優(yōu)化方法的過程到底是什么樣子的。

?

系列問題一：斐波那契數(shù)列問題

在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）根據(jù)定義，前十項為1, 1, 2, 3, 5, 8, 13, 21, 34, 55

問題一：

給定一個正整數(shù)n，求出斐波那契數(shù)列第n項（這時n較小）

解法一：最笨，效率最低，暴力遞歸，完全是抄定義。請看代碼

def f0(n):if n==1 or n==2:return 1return f(n-1)+f(n-2)

?

分析一下，為什么說遞歸效率很低呢？咱們來試著運行一下就知道了：

?

比如想求f(10)，計算機(jī)里怎么運行的？

?

每次要計算的函數(shù)量都是指數(shù)型增長，時間復(fù)雜度O(2^(N/2))<=T(N)<=O(2^N),效率很低。效率低的原因是，進(jìn)行了大量重復(fù)計算，比如圖中的f(8),f(7).....等等，你會發(fā)現(xiàn)f(8)其實早就算過了，但是你后來又要算一遍。

如果我們把計算的結(jié)果全都保存下來，按照一定的順序推出n項，就可以提升效率， 斐波那契（所有的一維）的順序已經(jīng)很明顯了，就是依次往下求。。

優(yōu)化1

def f1(n):if n==1 or n==2:return 1l=[0]*nl[0],l[1]=1,1for i in range(2,n):l[i]=l[i-1]+l[i-2]return l[-1]

?

時間復(fù)雜度o(n)，依次往下打表就行，空間o(n).

繼續(xù)優(yōu)化：既然只求第n項，而斐波那契又嚴(yán)格依賴前兩項，那我們何必記錄那么多值呢？記錄前兩項就行了

?

優(yōu)化2

def f2(n):a,b=1,1for i in range(n-1):a,b=b,a+breturn a

此次優(yōu)化做到了時間o(n),空間o(1)

附：這道題掌握到這里就可以了，但是其實有時間o(log2n)的方法

?

優(yōu)化三：

學(xué)習(xí)過線性代數(shù)的同學(xué)們能夠理解：

?

結(jié)合快速冪算法，我們可以在o(log2n)內(nèi)求出某個對象的n次冪。(在其它專題詳細(xì)講解)

注意：只有遞歸式不變，才可以用矩陣+快速冪的方法。

注：優(yōu)化三可能只有在面試上或競賽中用，當(dāng)然，快速冪還是要掌握的。

?

經(jīng)過這個最簡單的斐波那契，大家有沒有一點感覺了？

好，我們繼續(xù)往下走

(補充：pat、藍(lán)橋杯原題，讓求到一萬多位，結(jié)果模一個數(shù)。

可以每個結(jié)果都對這個數(shù)取模，否則爆內(nèi)存，另：對于有多組輸入并且所求結(jié)果類似的題，可以先求出所有結(jié)果存起來，然后直接接受每一個元素，在表中查找相應(yīng)答案)

?

問題二：

一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

依舊是找遞推關(guān)系，分析：跳一階，就一種方法，跳兩階，它可以一次跳兩個，也可以一個一個跳，所以有兩種，三個及三個以上，假設(shè)為n階，青蛙可以是跳一階來到這里，或者跳兩階來到這里，只有這兩種方法。它跳一階來到這里，說明它上一次跳到n-1階，同理，它也可以從n-2跳過來，f（n）為跳到n的方法數(shù)，所以，f(n)=f(n-1)+f(n-2)

和上題的優(yōu)化二類似。

因為遞推式?jīng)]變過，所以可以用優(yōu)化三

?

問題三：

我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？提示，大矩形看做是長度吧

請讀者自己先思考一下吧。。。仔細(xì)看題。。仔細(xì)思考

如果n是1，只有一種，豎著放唄；n是2，兩種：

，

n等于3，三種：

?

題意應(yīng)該理解了吧？

讀到這里，你們應(yīng)該能很快想到，依舊是斐波那契式遞歸啊。

對于n>=3:怎么能覆蓋到三？只有兩種辦法，從n-1的地方豎著放了一塊，或者從n-2的位置橫著放了兩塊唄。

和問題二的代碼都不用變。

?

問題四：

給定一個由0-9組成的字符串，1可以轉(zhuǎn)化成A，2可以轉(zhuǎn)化成B。依此類推。。25可以轉(zhuǎn)化成Y，26可以轉(zhuǎn)化成z，給一個字符串，返回能轉(zhuǎn)化的字母串的有幾種？

比如：123，可以轉(zhuǎn)化成

1 2 3變成ABC，

12 3變成LC，

1 23變成AW，三種，返回三，

99999，就一種：iiiii，返回一。

分析：求i位置及之前字符能轉(zhuǎn)化多少種。

兩種轉(zhuǎn)化方法，一，字符i自己轉(zhuǎn)換成自己對應(yīng)的字母，二，和前面那個數(shù)組成兩位數(shù)，然后轉(zhuǎn)換成對應(yīng)的字母

假設(shè)遍歷到i位置，判斷i-1位置和i位置組成的兩位數(shù)是否大于26，大于就沒有第二種方法，f(i)=f(i-1),想反，等于f(i-1)+f(i-2)

注意：遞歸式不確定，不能用矩陣快速冪

?

(這幾個題放到這里就是為了鍛煉找遞歸關(guān)系的能力，不要只會那個爛大街的斐波那契)

?

''' 斐波那契問題： 斐波納契數(shù)列以如下被以遞歸的方法定義： F(1)=1 F(2)=1 F(n)=F(n-1)+F(n-2)（n>=2，n∈N*） ''' #暴力抄定義,過多重復(fù)計算 def f0(n):if n==1 or n==2:return 1return f(n-1)+f(n-2) #記錄結(jié)果后依次遞推的優(yōu)化，時間O(N) def f1(n):if n==1 or n==2:return 1l=[0]*nl[0],l[1]=1,1for i in range(2,n):l[i]=l[i-1]+l[i-2]return l[-1] #既然嚴(yán)格依賴前兩項，不必記錄每一個結(jié)果，優(yōu)化空間到O(1) def f2(n):a,b=1,1for i in range(n-1):a,b=b,a+breturn a

?

總結(jié)

以上是生活随笔為你收集整理的简单暴力到dp的优化（萌新篇）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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