大廠動(dòng)態(tài)規(guī)劃面試匯總，重量級(jí)干貨，徹夜整理

注：本文是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 階樓梯，每次可上一階或兩階，求有多少種上樓梯的方法

先來分析下這個(gè)問題：

當(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ì)算問題，所以選擇動(dòng)態(tài)規(guī)劃算法。

層數(shù)	公式	種數(shù)
1	f(1)=1	1
2	f(2)=2	2
3	f(3)=f(1)+f(2)	3
4	f(4)=f(2)+f(3)	5

第三層：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)方程：

i值	j值	dp方程
i>0	j=0	dp[i][0] = dp[i?1][0] + grid[i][0]
i=0	j>0	dp[0][j] = dp[0][j?1] + grid[0][j]
i>0	j>0	dp[i][j] = min(dp[i?1][j], dp[i][j?1]) + grid[i][j]

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

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

代碼如下：

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

程序先把，第2行對(duì)應(yīng)的sum都求出來，再把第2列對(duì)應(yīng)的sum都求出來，最后求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的，說明可以組成 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ì)算出來，方式同上。

代碼如下：

等差遞減區(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ù)組	等差數(shù)列的數(shù)目	與上一組等差數(shù)列比較
1 2?3?	1	1 - 0 = 1
1?2 3 4	3	3 - 1 = 2
1?2 3 4?5?	6	6 - 3 = 3
1 2 3 4 5 6	10	10 - 6? =?4

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

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

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

下面看下代碼：

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

i值	子數(shù)組	dp[i]	res
i = 2	123	1	1
i = 3	123 234?1234	2	3
i = 4	123 234?1234 2345 12345	3	6
i = 5?	123 234?1234 2345 12345?23456?123456	4	10

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

最長回文子串

題目：求最長回文子串。輸入: "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ì)算出來了。

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

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

最長遞增子序列

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

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

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

代碼如下：

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

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

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

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

根據(jù)此依次類推到前面，d[0],d[1]…d[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]誰更大，然后取較大值。

代碼如下：

結(jié)尾

大廠面試算法是必考題，動(dòng)態(tài)規(guī)劃是?？嫉乃惴?，面試務(wù)必要掌握。希望大家能找滿意的工作。

長按二維碼，關(guān)注公眾號(hào)