遞歸與動(dòng)態(tài)規(guī)劃：基礎(chǔ)例題分析

個(gè)人簡(jiǎn)介：一個(gè)熱愛(ài)編程的在校生，我的世界不只有coding，還有writing。目前維護(hù)訂閱號(hào)「苦逼的碼農(nóng)」，專(zhuān)注于寫(xiě)「算法與數(shù)據(jù)結(jié)構(gòu)」，「Java」,「計(jì)算機(jī)網(wǎng)絡(luò)」。

ps:最近幾天正在刷一些有關(guān)動(dòng)態(tài)規(guī)劃的題，我會(huì)把自己學(xué)習(xí)時(shí)的想法以及做題的想法記錄下來(lái)。

題目1：一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法

對(duì)于這道題，我第一眼看到的想法是用遞歸的做法的，用遞歸的方法做題，我覺(jué)得最重要的就是找出 這個(gè)函數(shù)與下一個(gè)函數(shù)之間的關(guān)系 以及 一個(gè)函數(shù)體結(jié)束的臨界條件（即遞歸的結(jié)束）。

例如就本題而言,

1.第一步先找這個(gè)函數(shù)與下一個(gè)函數(shù)之間的關(guān)系：

假如有n個(gè)臺(tái)階，跳上一個(gè)n級(jí)的臺(tái)階的跳法總數(shù)為f(n).

我們?cè)谔倪^(guò)程中，每一次有兩種跳法，即跳一個(gè)或兩個(gè)臺(tái)階。

第一種跳法：第一次我跳了一個(gè)臺(tái)階，那么還剩下n-1個(gè)臺(tái)階還沒(méi)跳，剩下的n-1個(gè)臺(tái)階的跳法有f(n-1)種。

或者用

第二種跳法：第一次跳了兩個(gè)臺(tái)階，那么還剩下n-2個(gè)臺(tái)階還沒(méi)，剩下的n-2個(gè)臺(tái)階的跳法有f(n-2)種。

由此不難得出遞歸公式：f(n) = (n-1) + f(n-2);

2.第二步，找出遞歸的結(jié)束條件

當(dāng)n <= 0時(shí)，跳法為0，即此時(shí)f(n) = 0

當(dāng)只剩下一個(gè)臺(tái)階n = 1時(shí)，那么只有一種跳法，即f(1) = 1;

當(dāng)n = 2時(shí)，此時(shí)跳法為2種，即f(2) = 2;

函數(shù)與函數(shù)之間的關(guān)系以及遞歸的臨界條件都找出來(lái)了，那么接下來(lái)就可以開(kāi)始寫(xiě)代碼了。如下所示：

不過(guò)觀察一下你就會(huì)發(fā)現(xiàn)，其實(shí)在遞歸的過(guò)程中，有很多相同的)f(n)重復(fù)算。

如下圖：

算一下你就知道，時(shí)間復(fù)雜度是指數(shù)級(jí)別的。如果是比賽這樣做的話，絕對(duì)超時(shí)不通過(guò)

因此對(duì)于那些重復(fù)算過(guò)的，其實(shí)我們可以不用在重復(fù)遞歸來(lái)算它的，也就是所我們可以把f(n)算的結(jié)果一邊給保存起來(lái)，這種就是動(dòng)態(tài)規(guī)劃的思想。

也就是說(shuō)，我們可以把每次計(jì)算的結(jié)果保存中一個(gè)map容器里，把n作為key,f(n)作為value.然后每次要遞歸的時(shí)候，先查看一下這個(gè)f(n)我們是否已經(jīng)算過(guò)了，如果已經(jīng)算過(guò)了，我們直接從map容器里取出來(lái)返回去就可以了。如下：

這種方法會(huì)快很多很多。

實(shí)際上，對(duì)于f(n) = f(n-1) + f(n - 2)這種有遞推關(guān)系的題，其實(shí)和斐波那契數(shù)列很相似，還可以這樣做：

問(wèn)題2： 一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。 求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

分析，其實(shí)這道題和上面那道題一樣的，只是本來(lái)每次跳有兩種選擇，現(xiàn)在有n中選擇，即f(n) = f(n-1) + f(n - 2) + f(n-3)+.....+f(1);

因此做法如下：

如果你有其他想法，或者更完美的做法，歡迎指點(diǎn)江山。

下面為大家講解另外兩道，難度會(huì)提升一點(diǎn)點(diǎn)

數(shù)字三角形案例

題目描述 Description 下圖給出了一個(gè)數(shù)字三角形，請(qǐng)編寫(xiě)一個(gè)程序，計(jì)算從頂至底的某處的一條路徑，使該路徑所經(jīng)過(guò)的數(shù)字的總和最大。 注意：每一步可沿左斜線向下或右斜線向下

輸入描述： 第1行是輸入整數(shù)（如果該整數(shù)是0,就表示結(jié)束，不需要再處理），表示三角形行數(shù)n，然后是n行數(shù)樣例輸入： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

解題思路：對(duì)于這種有多種選擇的題，一般都可以使用遞歸的方法來(lái)做，上節(jié)講過(guò)，對(duì)于遞歸的題，最重要的 就是找出遞歸的兩個(gè)條件：

1. 兩個(gè)函數(shù)之間存在的關(guān)系 2. 遞歸結(jié)束的臨界條件

我們先來(lái)聲明一些變量來(lái)記錄一些東西

1. 用D(i,j)這個(gè)二維數(shù)組來(lái)記錄這個(gè)數(shù)字三角形，i表示第i行，j表示第j列，D(i,j)表示第i行j列這個(gè)點(diǎn)的值 2. MaxSum(i, j) : 從D(r,j)到底邊的各條路徑中，最佳路徑的數(shù)字之和(動(dòng)態(tài)規(guī)劃記錄狀態(tài)會(huì)用到) 3. state(i,j):用來(lái)記錄D(i,j)這個(gè)點(diǎn)是否計(jì)算過(guò)，如果還沒(méi)有計(jì)算過(guò)，則state(i,j) = -2,否則state(i,j) = MaxSum(i,j).

現(xiàn)在我們來(lái)尋找遞歸的兩個(gè)條件

1. 我們從第0行開(kāi)始一直走，顯然，當(dāng)我們走到最后一行時(shí)，遞歸結(jié)束，此時(shí)i = n-1(因?yàn)槲覀儚牡?行開(kāi)始算)

2. 當(dāng)我們處在D(i, j)這個(gè)點(diǎn)時(shí)，我們可以筆直往下走，也可以斜著往下走，有兩種走法 。我們的目標(biāo)時(shí)找出使總路徑較大的點(diǎn)，可以得到遞歸公式：

MaxSum(i,j) = max{MaxSum(i+1, j), MaxSum(i+1, j+1)} + D(i, j)

找出了這兩個(gè)條件，就好做了。代碼如下：

int MaxSum(int i, int j){ if(i == n-1) return D[i][j];//最底層，把該點(diǎn)的路徑值返回 int x = MaxSum(i + 1, j);//計(jì)算筆直向下走時(shí)的最優(yōu)路徑 int y = MaxSum(i + 1, j + 1);//計(jì)算斜向下走時(shí)的最優(yōu)路徑 return max(x,y) + D[i][j]; }

問(wèn)題所在：

和上次講的一樣，這種遞歸屬于暴力遞歸，會(huì)有很多重復(fù)計(jì)算的。和上次講的跳臺(tái)階那個(gè)類(lèi)似。時(shí)間復(fù)雜度是O(2的n次方)

重復(fù)計(jì)算的次數(shù)如下圖所示

下面我們采用動(dòng)態(tài)規(guī)劃的方法（遞歸動(dòng)態(tài)保存）

其實(shí)，我們可以每次在計(jì)算D(i,j)的時(shí)候，把計(jì)算出來(lái)的最優(yōu)解MasSum(i,j)保存起來(lái)， 下次需要的時(shí)候，先查看D(i,j)是否之前計(jì)算過(guò)，如果計(jì)算過(guò)，直接取出來(lái)就可以了。前面說(shuō)過(guò)我們把值存放在state(i,j)這個(gè)數(shù)組里。

代碼如下所示

` int MaxSum(int i, int j){ if(i == num)//臨界值 return D[i][j]; else if (state[i][j] != -2)//表示這個(gè) 點(diǎn)已經(jīng)計(jì)算過(guò)了 { return state[i][j]//直接取出返回 }else//否則的話就只好乖乖計(jì)算 { int x = MaxSum(i + 1, j); int y = MaxSum(i + 1, j + 1); state[i][j] = max(x,y) + D[i][j];//保存起來(lái) return state[i][j]; } }`

時(shí)間復(fù)雜度為O(n2)O(n2)，因?yàn)槿切蔚臄?shù)字總和為n(n+1)/2n(n+1)/2

ps:其實(shí)這道題也可以用遞推方法的動(dòng)態(tài)遞歸來(lái)接，從底部往上算起，有興趣的可以思考下。有興趣且想不出的可以問(wèn)我勒

二、

學(xué)這個(gè)最重要的就是多練些題了，剛開(kāi)始的時(shí)候盡量找寫(xiě)簡(jiǎn)單點(diǎn)的題，函數(shù)與函數(shù)之間的遞歸關(guān)系比較容易 找的題。下面找給大家介紹道題，和上次講的類(lèi)型比較一樣，算是比較基礎(chǔ)的題：

問(wèn)題： 我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？

還是我說(shuō)的一樣，找出

(1).遞歸的結(jié)束條件。

(2).函數(shù)與函數(shù)之間的遞歸關(guān)系

1.先找結(jié)束條件：

（1）當(dāng) n < 1時(shí)，顯然不需要用2*1塊覆蓋，應(yīng)該返回 0。

（2）當(dāng) n = 1時(shí)，只存在一種情況

（3）當(dāng) n = 2時(shí)，存在兩種情況

（4）當(dāng) n > 2時(shí)，顯然是需要橫著放和豎著，這時(shí)兩種情況交替放，就會(huì)產(chǎn)生遞歸的之間的函數(shù)關(guān)系（下圖是n=3的情況）

即 f(n) = f(n-1) + f(n-2). (有木發(fā)現(xiàn)這些題都很類(lèi)似，解法幾乎一樣)

代碼如下所示

int f(int n){ if(n < 1)return 0 ? ?else if(n == 1)return 1 ? ?else if(n == 2)return 2 ? ?else return f(n-1) + f(n-2) }

老規(guī)矩，這樣做，有很多重復(fù)算的，采用動(dòng)態(tài)記錄的方法。以n為key,f(n)為value保存在map容器中

Map m = new HashMap<>(); int f5(int n){ if(n < 1){ ? ? ? ? ? ?return 0; ? ? ? ?} ? ? ? ?else if(n == 1){ ? ? ? ? ? ?return 1; ? ? ? ?}else if(n == 2){ ? ? ? ? ? ?return 2; ? ? ? ?}else{ ? ? ? ? ? ?if(m.containsKey(n)){ ? ? ? ? ? ? ? ?return m.get(n); ? ? ? ? ? ?}else{ ? ? ? ? ? ? ? ?int sum = f5(n-1) + f5(n-2); ? ? ? ? ? ? ? ?map.put(n, sum); ? ? ? ? ? ? ? ?return sum; ? ? ? ? ? ?} ? ? ? ?} ? ?}