概論

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

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

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

輸入數(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ù)組中的一個連續(xù)的區(qū)間，而子序列并沒有這樣一個要求。

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

為什么要說這個？

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

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

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

題目分析

最長上升子序列

LeetCode 第 300 號問題：最長上升子序列。

題目描述

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

示例:

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

說明:

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

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

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

題目解析

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

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

問題拆解

我們要求解的問題是 “數(shù)組中最長遞增子序列”，一個子序列雖然不是連續(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 個位置中，哪一個位置可以和當(dāng)前位置拼接在一起，這樣就可以把第 i 個問題拆解成思考之前 i - 1 個問題，注意這里我們并不是不考慮起始位置，在遍歷的過程中我們其實(shí)已經(jīng)考慮過了。

狀態(tài)定義

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

遞推方程

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

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

實(shí)現(xiàn)

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

最后提一下，對于這道題來說，這種方法其實(shí)不是最優(yōu)的，但是在這里的話就不展開講了，理解序列類動態(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 號問題：粉刷房子。

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

題目描述

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

當(dāng)然，因?yàn)槭袌錾喜煌伾推岬膬r格不同，所以房子粉刷成不同顏色的花費(fèi)成本也是不同的。每個房子粉刷成不同顏色的花費(fèi)是以一個 n x 3 的矩陣來表示的。

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

注意：

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

示例：

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

題目解析

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

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

問題拆解

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

狀態(tài)定義

通過之前的問題拆解步驟，狀態(tài)可以定義成 dp[i][k]，表示如果第 i 個房子選擇第 k 個顏色，那么從 0 到 i 個房子的最小花費(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 個房子并不存在 i - 1 的情況，因此我們可以把第 0 個房子的最小花費(fèi)存在狀態(tài)數(shù)組中，當(dāng)然你也可以多開一格 dp 狀態(tài)，其實(shí)都是一樣的。

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

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

另外對于題目的分類其實(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 號問題：粉刷房子II。

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

題目描述

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

當(dāng)然，因?yàn)槭袌錾喜煌伾推岬膬r格不同，所以房子粉刷成不同顏色的花費(fèi)成本也是不同的。每個房子粉刷成不同顏色的花費(fèi)是以一個 n x k 的矩陣來表示的。

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

注意：

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

示例：

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

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

題目解析

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

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

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

其實(shí)這是可以優(yōu)化的，我們只需要在第 i - 1 個位置的狀態(tài)中找到最大值和次大值，在選擇第 i 個房子的顏色的時候，我們看當(dāng)前顏色是不是和最大值的顏色相重，不是的話直接加上最大值，如果相重的話，我們就加上次大值，這樣一來，我們把兩個嵌套的循環(huán)，拆開成兩個平行的循環(huán)，時間復(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 號問題：打家劫舍。

題目描述

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

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

示例 1:

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

示例 2:

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

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

題目解析

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

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

問題拆解

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

狀態(tài)定義

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

遞推方程

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

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

實(shí)現(xiàn)

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

參考代碼

//@五分鐘學(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 號問題：打家劫舍II。

題目描述

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

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

示例 1:

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

示例 2:

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

題目解析

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

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

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

這里有一個邊界條件就是，當(dāng)只有一個房子的時候，我們直接輸出結(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é)

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

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