概論

上一篇文章 我們分析了矩陣類動(dòng)態(tài)規(guī)劃，說到這類動(dòng)態(tài)規(guī)劃通常在一個(gè)矩陣中進(jìn)行，我們只需要考慮當(dāng)前位置的信息即可，分析并定義狀態(tài)的時(shí)候，也只需要分析當(dāng)前位置和其相鄰位置的關(guān)系，通常這樣做就可以達(dá)到拆解問題的目的。

這次再來看一類動(dòng)態(tài)規(guī)劃問題，序列類動(dòng)態(tài)規(guī)劃問題，這類動(dòng)態(tài)規(guī)劃問題較為普遍，分析難度相比之前也略有提升，通常問題的輸入?yún)?shù)會(huì)涉及數(shù)組或是字符串。

在開始之前，先解釋一下子數(shù)組（子串）和子序列的區(qū)別，你可以看看下面這個(gè)例子：

輸入數(shù)組：[1,2,3,4,5,6,7,8,9] 子數(shù)組：[2,3,4],[5,6,7],[6,7,8,9],... 子序列：[1,5,9],[2,3,6],[1,8,9],[7,8,9],...

可以看到的是，子數(shù)組必須是數(shù)組中的一個(gè)連續(xù)的區(qū)間，而子序列并沒有這樣一個(gè)要求。

你只需要保證子序列中的元素的順序和原數(shù)組中元素的順序一致即可，例如，在原數(shù)組中，元素 1 出現(xiàn)在元素 9 之前，那么在子序列中，如果這兩個(gè)元素同時(shí)出現(xiàn)，那么 1 也必須在 9 之前。

為什么要說這個(gè)？

不知道你有沒有發(fā)現(xiàn)，這里的子數(shù)組的問題和我們前面提到的矩陣類動(dòng)態(tài)規(guī)劃的分析思路很類似，只需要考慮當(dāng)前位置，以及當(dāng)前位置和相鄰位置的關(guān)系。

通過這樣的分析就可以把之前講的內(nèi)容和今天要介紹的內(nèi)容關(guān)聯(lián)起來了，相比矩陣類動(dòng)態(tài)規(guī)劃，序列類動(dòng)態(tài)規(guī)劃最大的不同在于，對(duì)于第 i 個(gè)位置的狀態(tài)分析，它不僅僅需要考慮當(dāng)前位置的狀態(tài)，還需要考慮前面 i - 1 個(gè)位置的狀態(tài)，這樣的分析思路其實(shí)可以從子序列的性質(zhì)中得出。

對(duì)于這類問題的問題拆解，有時(shí)并不是那么好發(fā)現(xiàn)問題與子問題之間的聯(lián)系，但是通常來說思考的方向其實(shí)在于尋找當(dāng)前狀態(tài)和之前所有狀態(tài)的關(guān)系，我們通過幾個(gè)非常經(jīng)典的動(dòng)態(tài)規(guī)劃問題來一起看看。

題目分析

最長(zhǎng)上升子序列

LeetCode 第 300 號(hào)問題：最長(zhǎng)上升子序列。

題目描述

給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長(zhǎng)上升子序列的長(zhǎng)度。

示例:

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

說明:

可能會(huì)有多種最長(zhǎng)上升子序列的組合，你只需要輸出對(duì)應(yīng)的長(zhǎng)度即可。

你算法的時(shí)間復(fù)雜度應(yīng)該為 O(n2) 。

進(jìn)階:你能將算法的時(shí)間復(fù)雜度降低到 O(n log n) 嗎?

題目解析

給定一個(gè)數(shù)組，求最長(zhǎng)遞增子序列。因?yàn)槭亲有蛄?，這樣對(duì)于每個(gè)位置的元素其實(shí)都存在兩種可能，就是選和不選，如果我們用暴力的解法，枚舉出所有的子序列，然后判斷他們是不是遞增的，選取最大的遞增序列，這樣做的話，時(shí)間復(fù)雜度是 O(2^n)，顯然不高效。

那這里我們就需要思考用動(dòng)態(tài)規(guī)劃進(jìn)行優(yōu)化，我們按之前的四個(gè)步驟來具體分析一下：

問題拆解

我們要求解的問題是 “數(shù)組中最長(zhǎng)遞增子序列”，一個(gè)子序列雖然不是連續(xù)的區(qū)間，但是它依然有起點(diǎn)和終點(diǎn)，比如：

[10,9,2,5,3,7,101,18] 子序列[2,3,7,18]的起始位置是2，終止位置是18 子序列[5,7,101]的起始位置是5，終止位置是101

如果我們確定終點(diǎn)位置，然后去看前面 i - 1 個(gè)位置中，哪一個(gè)位置可以和當(dāng)前位置拼接在一起，這樣就可以把第 i 個(gè)問題拆解成思考之前 i - 1 個(gè)問題，注意這里我們并不是不考慮起始位置，在遍歷的過程中我們其實(shí)已經(jīng)考慮過了。

狀態(tài)定義

問題拆解中我們提到 “第 i 個(gè)問題和前 i - 1 個(gè)問題有關(guān)”，也就是說 “如果我們要求解第 i 個(gè)問題的解，那么我們必須考慮前 i - 1 個(gè)問題的解”，我們定義dp[i] 表示以位置 i 結(jié)尾的子序列的最大長(zhǎng)度，也就是說 dp[i] 里面記錄的答案保證了該答案表示的子序列以位置 i 結(jié)尾。

遞推方程

對(duì)于 i 這個(gè)位置，我們需要考慮前 i - 1 個(gè)位置，看看哪些位置可以拼在 i 位置之前，如果有多個(gè)位置可以拼在 i 之前，那么必須選最長(zhǎng)的那個(gè)，這樣一分析，遞推方程就有了：

dp[i]=Math.max(dp[j],...,dp[k])+1, 其中inputArray[j]

實(shí)現(xiàn)

在實(shí)現(xiàn)這里，我們需要考慮狀態(tài)數(shù)組的初始化，因?yàn)閷?duì)于每個(gè)位置，它本身其實(shí)就是一個(gè)序列，因此所有位置的狀態(tài)都可以初始化為 1。

最后提一下，對(duì)于這道題來說，這種方法其實(shí)不是最優(yōu)的，但是在這里的話就不展開講了，理解序列類動(dòng)態(tài)規(guī)劃的解題思路是關(guān)鍵。

參考代碼

//@五分鐘學(xué)算法 //www.cxyxiaowu.com publicintlengthOfLIS(int[]nums){ if(nums==null||nums.length==0){ return0; } //dp[i]->thelongestlengthsequencefrom0-i,andmustincludenums[i] int[]dp=newint[nums.length]; Arrays.fill(dp,1); intmax=0; for(inti=0;inums[j]){ dp[i]=Math.max(dp[j]+1,dp[i]); } } max=Math.max(max,dp[i]); } returnmax; }粉刷房子

LeetCode 第 256 號(hào)問題：粉刷房子。

注意：本題為 LeetCode 的付費(fèi)題目，需要開通會(huì)員才能解鎖查看與提交代碼。

題目描述

假如有一排房子，共 n 個(gè)，每個(gè)房子可以被粉刷成紅色、藍(lán)色或者綠色這三種顏色中的一種，你需要粉刷所有的房子并且使其相鄰的兩個(gè)房子顏色不能相同。

當(dāng)然，因?yàn)槭袌?chǎng)上不同顏色油漆的價(jià)格不同，所以房子粉刷成不同顏色的花費(fèi)成本也是不同的。每個(gè)房子粉刷成不同顏色的花費(fèi)是以一個(gè) n x 3 的矩陣來表示的。

例如，costs[0][0]表示第 0 號(hào)房子粉刷成紅色的成本花費(fèi)；costs[1][2]表示第 1 號(hào)房子粉刷成綠色的花費(fèi)，以此類推。請(qǐng)你計(jì)算出粉刷完所有房子最少的花費(fèi)成本。

注意：

所有花費(fèi)均為正整數(shù)。

示例：

輸入:[[17,2,17],[16,16,5],[14,3,19]] 輸出:10 解釋:將0號(hào)房子粉刷成藍(lán)色，1號(hào)房子粉刷成綠色，2號(hào)房子粉刷成藍(lán)色。 最少花費(fèi):2+5+3=10。

題目解析

給 n 個(gè)房子刷油漆，有三種顏色的油漆可以刷，必須保證相鄰房子的顏色不能相同，輸入是一個(gè) n x 3 的數(shù)組，表示每個(gè)房子使用每種油漆所需要花費(fèi)的價(jià)錢，求刷完所有房子的最小價(jià)值。

還是按原來的思考方式走一遍：

問題拆解

對(duì)于每個(gè)房子來說，都可以使用三種油漆當(dāng)中的一種，如果說不需要保證相鄰的房子的顏色必須不同，那么整個(gè)題目會(huì)變得非常簡(jiǎn)單，每個(gè)房子直接用最便宜的油漆刷就好了，但是加上這個(gè)限制條件，你會(huì)發(fā)現(xiàn)刷第 i 個(gè)房子的花費(fèi)其實(shí)是和前面 i - 1 個(gè)房子的花費(fèi)以及選擇相關(guān)，如果說我們需要知道第 i 個(gè)房子使用第 k 種油漆的最小花費(fèi)，那么你其實(shí)可以思考第 i - 1 個(gè)房子如果不用該油漆的最小花費(fèi)，這個(gè)最小花費(fèi)是考慮從 0 到當(dāng)前位置所有的房子的。

狀態(tài)定義

通過之前的問題拆解步驟，狀態(tài)可以定義成 dp[i][k]，表示如果第 i 個(gè)房子選擇第 k 個(gè)顏色，那么從 0 到 i 個(gè)房子的最小花費(fèi)

遞推方程

基于之前的狀態(tài)定義，以及相鄰的房子不能使用相同的油漆，那么遞推方程可以表示成：

dp[i][k]=Math.min(dp[i-1][l],...,dp[i-1][r])+costs[i][k]，l!=k,r!=k

實(shí)現(xiàn)

因?yàn)槲覀円紤] i - 1 的情況，但是第 0 個(gè)房子并不存在 i - 1 的情況，因此我們可以把第 0 個(gè)房子的最小花費(fèi)存在狀態(tài)數(shù)組中，當(dāng)然你也可以多開一格 dp 狀態(tài)，其實(shí)都是一樣的。

對(duì)于這道題目，你可能會(huì)問這不是和矩陣類動(dòng)態(tài)規(guī)劃類似嗎？

如果單從房子來考慮的確是，但是對(duì)于顏色的話，我們必須考慮考慮相鄰房子的所有顏色，這就有點(diǎn)序列的意思在里面了。

另外對(duì)于題目的分類其實(shí)沒有嚴(yán)格的限定，主要是為了把相類似的問題放在一起，這樣有便于分析問題思路。

參考代碼

//@五分鐘學(xué)算法 //www.cxyxiaowu.com publicintminCost(int[][]costs){ if(costs==null||costs.length==0){ return0; } intn=costs.length; int[][]dp=newint[n][3]; for(inti=0;i

LeetCode 第 265 號(hào)問題：粉刷房子II。

注意：本題為 LeetCode 的付費(fèi)題目，需要開通會(huì)員才能解鎖查看與提交代碼。

題目描述

假如有一排房子，共 n 個(gè)，每個(gè)房子可以被粉刷成 k 種顏色中的一種，你需要粉刷所有的房子并且使其相鄰的兩個(gè)房子顏色不能相同。

當(dāng)然，因?yàn)槭袌?chǎng)上不同顏色油漆的價(jià)格不同，所以房子粉刷成不同顏色的花費(fèi)成本也是不同的。每個(gè)房子粉刷成不同顏色的花費(fèi)是以一個(gè) n x k 的矩陣來表示的。

例如，costs[0][0] 表示第 0 號(hào)房子粉刷成 0 號(hào)顏色的成本花費(fèi)；costs[1][2] 表示第 1 號(hào)房子粉刷成 2 號(hào)顏色的成本花費(fèi)，以此類推。請(qǐng)你計(jì)算出粉刷完所有房子最少的花費(fèi)成本。

注意：

所有花費(fèi)均為正整數(shù)。

示例：

輸入:[[1,5,3],[2,9,4]] 輸出:5 解釋:將0號(hào)房子粉刷成0號(hào)顏色，1號(hào)房子粉刷成2號(hào)顏色。最少花費(fèi):1+4=5; 或者將0號(hào)房子粉刷成2號(hào)顏色，1號(hào)房子粉刷成0號(hào)顏色。最少花費(fèi):3+2=5.

進(jìn)階：
您能否在 O(nk) 的時(shí)間復(fù)雜度下解決此問題？

題目解析

上面那道題目的 follow up，現(xiàn)在不是三種油漆，而是 k 種油漆。

其實(shí)解題思路還是不變。

對(duì)于第 i 個(gè)房子的每種顏色，我們對(duì)比看第 i - 1 個(gè)房子的 k 種油漆，找到不相重的最小值就好，但是這里的時(shí)間復(fù)雜度是 O(n*k^2)。

其實(shí)這是可以優(yōu)化的，我們只需要在第 i - 1 個(gè)位置的狀態(tài)中找到最大值和次大值，在選擇第 i 個(gè)房子的顏色的時(shí)候，我們看當(dāng)前顏色是不是和最大值的顏色相重，不是的話直接加上最大值，如果相重的話，我們就加上次大值，這樣一來，我們把兩個(gè)嵌套的循環(huán)，拆開成兩個(gè)平行的循環(huán)，時(shí)間復(fù)雜度降至 O(n*k)。

參考代碼(優(yōu)化前)

//@五分鐘學(xué)算法 //www.cxyxiaowu.com publicintminCostII(int[][]costs){ if(costs.length==0||costs[0].length==0){ return0; } intn=costs.length,k=costs[0].length; int[][]dp=newint[n][k]; for(inti=1;i

參考代碼(優(yōu)化后)

//@五分鐘學(xué)算法 //www.cxyxiaowu.com publicintminCostII(int[][]costs){ if(costs.length==0||costs[0].length==0){ return0; } intn=costs.length,k=costs[0].length; int[][]dp=newint[n][k]; for(inti=1;idp[i-1][l]){ min2=min1; min1=dp[i-1][l]; minIndex=l; }elseif(min2>dp[i-1][l]){ min2=dp[i-1][l]; } } for(intj=0;j

LeetCode 第 198 號(hào)問題：打家劫舍。

題目描述

你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額。

示例 1:

輸入:[1,2,3,1] 輸出:4 解釋:偷竊 1 號(hào)房屋(金額= 1)，然后偷竊 3 號(hào)房屋(金額= 3)。 偷竊到的最高金額= 1 + 3 = 4 。

示例 2:

輸入:[2,7,9,3,1] 輸出:12 解釋:偷竊 1 號(hào)房屋(金額= 2), 偷竊 3 號(hào)房屋(金額= 9)，接著偷竊 5 號(hào)房屋(金額= 1)。 偷竊到的最高金額= 2 + 9 + 1 = 12 。

圖片來源：https://github.com/azl397985856/leetcode

題目解析

還是房子，這次不是刷房子，而是搶房子。。。：）

條件和前面類似，就是相鄰的房子不能搶。老樣子，四個(gè)步驟走一遍：

問題拆解

如果我們要求解搶完 n 個(gè)房子所獲得的最大收入，因?yàn)轭}目的要求，我們可以思考第 i 個(gè)房子是否應(yīng)該搶，如果要搶，那么第 i - 1 個(gè)房子就不能搶，我們只能考慮搶第 i - 2 個(gè)房子。如果不搶，那么就可以搶第 i - 1 個(gè)房子，這樣一來，第 i 個(gè)房子就和第 i - 1 個(gè)房子，以及第 i - 2 個(gè)房子聯(lián)系上了。

狀態(tài)定義

通過之前的問題拆解，我們知道，如果我們從左到右去搶房子，搶到當(dāng)前房子可以獲得的最大值其實(shí)是和搶到前兩個(gè)房子可以獲得的最大值有關(guān)，因此我們可以用dp[i] 表示搶到第 i 個(gè)房子可以獲得的最大值

遞推方程

如果我們搶第 i 個(gè)房子，那么我們就只能去考慮第 i - 2 個(gè)房子，如果不搶，那么我們可以考慮第 i - 1 個(gè)房子，于是遞推方程就有了：

dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1])

實(shí)現(xiàn)

因?yàn)榈?i 個(gè)位置和前面的兩個(gè)位置都有關(guān)，這個(gè)時(shí)候我們可以把狀態(tài)多開一格，dp[0] 表示的是一個(gè)房子都不搶的狀態(tài)，dp[1] 就是最左邊的房子獲得的最大價(jià)值，這個(gè)房子之前也沒有其他的房子，直接搶即可。

參考代碼

//@五分鐘學(xué)算法 //www.cxyxiaowu.com publicintrob(int[]nums){ if(nums==null||nums.length==0){ return0; } intn=nums.length; int[]dp=newint[n+1]; dp[1]=nums[0]; for(inti=2;i<=?n;?++i)?{ ????????dp[i]?=?Math.max(dp[i?-?1],?dp[i?-?2]?+?nums[i?-?1]); ????} ????return?dp[n]; }打家劫舍II?

LeetCode 第 213 號(hào)問題：打家劫舍II。

題目描述

你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋，每間房?jī)?nèi)都藏有一定的現(xiàn)金。這個(gè)地方所有的房屋都圍成一圈，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的。同時(shí)，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額。

示例 1:

輸入:[2,3,2] 輸出:3 解釋:你不能先偷竊 1 號(hào)房屋（金額= 2），然后偷竊 3 號(hào)房屋（金額= 2）, 因?yàn)樗麄兪窍噜彽摹?/p>

示例 2:

輸入:[1,2,3,1] 輸出:4 解釋:你可以先偷竊 1 號(hào)房屋（金額= 1），然后偷竊 3 號(hào)房屋（金額= 3）。 偷竊到的最高金額= 1 + 3 = 4 。

題目解析

前面那道題目的 follow up，問的是如果這些房子的排列方式是一個(gè)圓圈，其余要求不變，問該如何處理。

房子排列方式是一個(gè)圓圈意味著之前的最后一個(gè)房子和第一個(gè)房子之間產(chǎn)生了聯(lián)系，這里有一個(gè)小技巧就是我們線性考慮 [0, n - 2] 和 [1, n - 1]，然后求二者的最大值。

其實(shí)這么做的目的很明顯，把第一個(gè)房子和最后一個(gè)房子分開來考慮。實(shí)現(xiàn)上面我們可以直接使用之前的實(shí)現(xiàn)代碼。

這里有一個(gè)邊界條件就是，當(dāng)只有一個(gè)房子的時(shí)候，我們直接輸出結(jié)果即可。

參考代碼

//@五分鐘學(xué)算法 //www.cxyxiaowu.com publicintrob(int[]nums){ if(nums==null||nums.length==0){ return0; } if(nums.length==1){ returnnums[0]; } intn=nums.length; returnMath.max( robI(Arrays.copyOfRange(nums,0,n-1)), robI(Arrays.copyOfRange(nums,1,n)) ); } publicintrobI(int[]nums){ if(nums==null||nums.length==0){ return0; } intn=nums.length; int[]dp=newint[n+1]; dp[1]=nums[0]; for(inti=2;i<=?n;?++i)?{ ????????dp[i]?=?Math.max(dp[i?-?1],?dp[i?-?2]?+?nums[i?-?1]); ????} ????return?dp[n]; }

總結(jié)

序列類動(dòng)態(tài)規(guī)劃的系列問題還有很多，比如股票問題，這類問題通常會(huì)給你一個(gè)數(shù)組或者是字符串，在分析這些問題的時(shí)候，需要思考當(dāng)前狀態(tài)的選擇是否要基于前面的狀態(tài)，以及他們的關(guān)系是什么。

當(dāng)然這里還有挺多的優(yōu)化，比如動(dòng)態(tài)規(guī)劃的狀態(tài)數(shù)組的空間優(yōu)化，這些會(huì)在后面統(tǒng)一介紹，這里只需要熟悉動(dòng)態(tài)規(guī)劃的思考方向和方法即可。