概論

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

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

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

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

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

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

為什么要說這個？

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

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

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

題目分析

最長上升子序列

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

題目描述

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

示例:

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

說明:

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

你算法的時間復雜度應該為 O(n2) 。

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

題目解析

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

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

問題拆解

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

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

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

狀態(tài)定義

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

遞推方程

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

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

實現

在實現這里，我們需要考慮狀態(tài)數組的初始化，因為對于每個位置，它本身其實就是一個序列，因此所有位置的狀態(tài)都可以初始化為 1。

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

參考代碼

//@五分鐘學算法 //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 的付費題目，需要開通會員才能解鎖查看與提交代碼。

題目描述

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

當然，因為市場上不同顏色油漆的價格不同，所以房子粉刷成不同顏色的花費成本也是不同的。每個房子粉刷成不同顏色的花費是以一個 n x 3 的矩陣來表示的。

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

注意：

所有花費均為正整數。

示例：

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

題目解析

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

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

問題拆解

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

狀態(tài)定義

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

遞推方程

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

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

實現

因為我們要考慮 i - 1 的情況，但是第 0 個房子并不存在 i - 1 的情況，因此我們可以把第 0 個房子的最小花費存在狀態(tài)數組中，當然你也可以多開一格 dp 狀態(tài)，其實都是一樣的。

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

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

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

參考代碼

//@五分鐘學算法 //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 的付費題目，需要開通會員才能解鎖查看與提交代碼。

題目描述

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

當然，因為市場上不同顏色油漆的價格不同，所以房子粉刷成不同顏色的花費成本也是不同的。每個房子粉刷成不同顏色的花費是以一個 n x k 的矩陣來表示的。

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

注意：

所有花費均為正整數。

示例：

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

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

題目解析

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

其實解題思路還是不變。

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

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

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

//@五分鐘學算法 //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)化后)

//@五分鐘學算法 //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è)的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

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

示例 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 個房子所獲得的最大收入，因為題目的要求，我們可以思考第 i 個房子是否應該搶，如果要搶，那么第 i - 1 個房子就不能搶，我們只能考慮搶第 i - 2 個房子。如果不搶，那么就可以搶第 i - 1 個房子，這樣一來，第 i 個房子就和第 i - 1 個房子，以及第 i - 2 個房子聯(lián)系上了。

狀態(tài)定義

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

遞推方程

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

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

實現

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

參考代碼

//@五分鐘學算法 //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è)的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都圍成一圈，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

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

示例 1:

輸入:[2,3,2] 輸出:3 解釋:你不能先偷竊 1 號房屋（金額= 2），然后偷竊 3 號房屋（金額= 2）, 因為他們是相鄰的。

示例 2:

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

題目解析

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

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

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

這里有一個邊界條件就是，當只有一個房子的時候，我們直接輸出結果即可。

參考代碼

//@五分鐘學算法 //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]; }

總結

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

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