注：本文是BAT真題收錄很值得大家花心思看完，看完會(huì)有收獲。

前言

算法是面試大公司必考的項(xiàng)目，所以面試前準(zhǔn)備好算法至關(guān)重要，今天整理的常見的動(dòng)態(tài)規(guī)劃題目，希望可以幫到大家。

要想學(xué)習(xí)其他絕世武功，要先打好基礎(chǔ)。算法屬于內(nèi)功，則更為重要。

強(qiáng)盜搶劫

題目：強(qiáng)盜搶劫一排房間，每個(gè)房間都有錢，不能搶劫兩個(gè)相鄰的房間，要求搶的錢最多。數(shù)組如：[2,7,9,3,1]

思路：當(dāng)輸入房間數(shù)為0,1,2時(shí)，這個(gè)很好判斷，當(dāng)輸入房間數(shù)字大于3時(shí)，就要用到動(dòng)態(tài)規(guī)劃了，方程是:

dp[i]是當(dāng)搶到第i個(gè)數(shù)時(shí)，能搶到最大值，從局部最大值推到最終結(jié)果最大。

假如搶到第5個(gè)房間，那么第5個(gè)房間有二種情況，搶不和不被搶，因?yàn)橹荒芨舴块g。

如果搶到第4個(gè)房間，有個(gè)最大值；搶到第3個(gè)房間，有個(gè)最大值。

如果加上第3房間最大值，加上第5房間的最大值，大于搶到第4個(gè)房間時(shí)的最大時(shí)。那就搶3,5而不搶4，反而，就按搶4的策略。

這樣從前往后推，最后的結(jié)果一定是最大的。

代碼如下：

跳臺(tái)階

題目描述：有 N 階樓梯，每次可上一階或兩階，求有多少種上樓梯的方法

先來(lái)分析下這個(gè)問(wèn)題：

當(dāng)N=1時(shí)，這個(gè)很好理解，只能跨1步這一種了

當(dāng)N=2時(shí)，你每次可以跨1步或2步，那就是走2步或走兩個(gè)1步

當(dāng)N=3時(shí)，因?yàn)槟憧梢钥?步或2步，那你在臺(tái)階1或2都能行。要計(jì)算到臺(tái)階1有多少種走法，到臺(tái)階2有多少種走法，然后2種相加，依次逆推。

當(dāng)N=4時(shí)，你在臺(tái)階2或3都能行，計(jì)算到臺(tái)階2有多少種走法，到臺(tái)階3有多少種走法，然后2者相加，依次逆推。

總結(jié)如下：你會(huì)發(fā)現(xiàn)，這是斐波拉切數(shù)列，使用遞歸出現(xiàn)重復(fù)計(jì)算問(wèn)題，所以選擇動(dòng)態(tài)規(guī)劃算法。

第三層：3種（在第一層走2步或在第二層走1步）

第四層：5種（在第二層走2步或在第三層走1步）

i,j首先賦邊界值，res保存i+j的值，每次前進(jìn)，i,j,res的值都會(huì)被賦到前面結(jié)果。

上面的算法是底向上，遞歸相當(dāng)于自頂向下，避免了重復(fù)計(jì)算。

矩形最小路徑和

題目：
給定一個(gè)，包含非負(fù)整數(shù)的 m x n 網(wǎng)格。請(qǐng)找出一條，從左上角到右下角的路徑。使得路徑上，所有數(shù)字總和為最小，每次只能向下，或者向右移動(dòng)一步。

輸入:[[1,3,1],
[1,5,1],
[4,2,1]]
輸出: 7
解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小。

先看動(dòng)態(tài)方程：

說(shuō)明：因?yàn)?i=0 和 j=0 是臨界條件，所以要先求出來(lái)。當(dāng) i>0 和 j>0 時(shí)，看如上數(shù)組，5 可以由上方3，或者左方 1 走過(guò)來(lái)。

當(dāng)走5的時(shí)候，要選取上方3對(duì)應(yīng)的dp，與左方1 對(duì)應(yīng)的dp進(jìn)行比較，選擇較小值累加，這樣走出來(lái)的才是最小值。最后推出，到右下角的最小值。

代碼如下：

sum用來(lái)存儲(chǔ)，從[0][0]到sum[i][j]路徑的最小和，看看每次sum的變化，sum[1][1]=7意思是，從[0][0]到[1][1]路徑最小和是7。

程序先把，第2行對(duì)應(yīng)的sum都求出來(lái)，再把第2列對(duì)應(yīng)的sum都求出來(lái)，最后求sum[2][2]就很容易了。

最后，sum[i-1][j-1]就是推出的最小值，上述代碼就是dp方程的實(shí)現(xiàn)。

劃分?jǐn)?shù)組為兩個(gè)相等的子集

題目：輸入：[1, 5, 11, 5]， 輸出：[1, 5, 5]和[11]

思路是，相對(duì)數(shù)組中每個(gè)數(shù)求dp，最后就會(huì)找到dp[target]是否為true。

如果 dp[j - nums[i]] 為true的，說(shuō)明可以組成 j-nums[i]這個(gè)數(shù)，再加上nums[i]，就可以組成數(shù)字j。

當(dāng)j = target是同樣道理，要想找到dp[target]為true，就找到數(shù)組中，幾個(gè)值的和為target時(shí)，對(duì)應(yīng)下標(biāo)的dp值為true，這樣反推dp[target]為true。

代碼如下：

乘積最大連續(xù)子數(shù)組

題目：
輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)，或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的最大值。

例如數(shù)組：arr[]={1, 2, 3, -2, 4, -3 } 最大子數(shù)組為 {1, 2, 3, -2, 4} 和為8。

思路：fmax(i) 表示，以第 i 個(gè)元素結(jié)尾的，乘積最大子數(shù)組的乘積，fmin(i) 表示，以第 i 個(gè)元素結(jié)尾的，乘積最小子數(shù)組的乘積。

這里分為最大和最小是因?yàn)閿?shù)組可能存在負(fù)數(shù)，最大值乘以負(fù)數(shù)變成較小值，最小值乘以一個(gè)負(fù)數(shù)也可能變成最大值。

比較方程是：當(dāng)前數(shù)乘以上一個(gè)最大值，當(dāng)前值，當(dāng)前數(shù)乘以上一個(gè)最小值。這三者比較，其中的最大值，就是我們要的最大值。

同樣，每次也要把最小值計(jì)算出來(lái)，方式同上。

代碼如下：

等差遞減區(qū)間的個(gè)數(shù)

題目：求一個(gè)數(shù)組中等差遞減區(qū)間個(gè)數(shù)，等差數(shù)列必須是連續(xù)的。

例子：A = [1, 2, 3, 4]，個(gè)數(shù)為3，分別是:[1, 2, 3], [2, 3, 4]

等差數(shù)列公式：

先看一個(gè)表：

其實(shí)仔細(xì)觀察，發(fā)現(xiàn)這是一個(gè)斐波拉切數(shù)列，0,1….n-2數(shù)的求和，動(dòng)態(tài)規(guī)劃找到方程了，就發(fā)現(xiàn)非常簡(jiǎn)單了。

這就是規(guī)律，但需要自己去發(fā)現(xiàn)規(guī)律，有些題目咋看一臉懵逼，仔細(xì)看就會(huì)發(fā)現(xiàn)其中的規(guī)律。

dp[i] 表示到i位置時(shí)，子數(shù)組的個(gè)數(shù)。數(shù)組長(zhǎng)度大于3。

下面看下代碼：

下面再看代碼執(zhí)行值的變化過(guò)程：

很明顯，就是0,1….n-2數(shù)的求和。

最長(zhǎng)回文子串

題目：求最長(zhǎng)回文子串。輸入: "babad"，輸出: "bab"。注意: "aba" 也是一個(gè)有效答案。

dp[i][j]表示，字符s從下標(biāo)i到下標(biāo)j，是否為回文串。

如果bab是回文串，那么ababa也是回文串。因?yàn)?，在兩邊增加了相同的?shù)。同理，可以給出動(dòng)態(tài)方程：

下面看下代碼：

這段代碼用利用了dp[i + 1][j - 1]，其前面已經(jīng)計(jì)算出來(lái)了。

當(dāng)k = 4時(shí)，字符串最長(zhǎng)，最后符合條件的回文子串最長(zhǎng)。注意整個(gè)循環(huán)遍歷的過(guò)程，用k最為兩個(gè)下標(biāo)的間距，然后遍歷每種可能的結(jié)果，判斷是否回文。

最長(zhǎng)的子串最后判斷，將符合條件的子串保存起來(lái)。動(dòng)態(tài)規(guī)劃方程推測(cè)極為重要。

最長(zhǎng)遞增子序列

求一個(gè)數(shù)組的最長(zhǎng)自增子序列。

輸入: [10,9,2,5,3,7,101,18]，輸出: 4。

解釋: 最長(zhǎng)的上升子序列是 [2,3,7,101]，它的長(zhǎng)度是 4。

代碼如下：

dp[i]表示以a[i]這個(gè)元素結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度。

想求 dp[5] 的值，也就是想求以 nums[5] 為結(jié)尾，其最長(zhǎng)遞增子序列。

nums[5] = 3，既然是遞增子序列。我們只要找到，前面那些結(jié)尾比 3 小的子序列，然后把 3 接到最后，就可以形成新的遞增子序列，而且這個(gè)新的子序列長(zhǎng)度加一。

當(dāng)然，可能形成很多種新的子序列，但是我們只要最長(zhǎng)的，把最長(zhǎng)子序列的長(zhǎng)度作為 dp[5] 的值即可。

根據(jù)此依次類推到前面，d[0],d[1]…d[i]都是這樣求出來(lái)的，看來(lái)動(dòng)態(tài)規(guī)劃有些是逆推的。

最大子序和

給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

輸入: [-2,1,-3,4,-1,2,1,-5,4]，輸出: 6，解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6

解決思路：動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃方程：

動(dòng)態(tài)規(guī)劃：定義dp[i]表示為nums[i]為結(jié)尾的[連續(xù)子數(shù)組的最大和。

當(dāng)遍歷到nums[i]時(shí)，我們需要比較nums[i]和dp[i-1]+nums[i]誰(shuí)更大，然后取較大值。

代碼如下：

責(zé)任編輯：lq