動(dòng)態(tài)規(guī)劃系列一：爬樓梯1.1 概念講解講解動(dòng)態(tài)規(guī)劃的資料很多，官方的定義是指把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解。概念中的各階段之間的關(guān)系，其實(shí)指的就是狀態(tài)轉(zhuǎn)移方程。很多人覺得DP難（下文統(tǒng)稱動(dòng)態(tài)規(guī)劃為DP），根本原因是因?yàn)镈P區(qū)別于一些固定形式的算法（比如DFS、二分法、KMP），沒有實(shí)際的步驟規(guī)定第一步第二步來做什么，所以準(zhǔn)確的說，DP其實(shí)是一種解決問題的思想。 這種思想的本質(zhì)是：一個(gè)規(guī)模比較大的問題（可以用兩三個(gè)參數(shù)表示的問題），可以通過若干規(guī)模較小的問題的結(jié)果來得到的（通常會(huì)尋求到一些特殊的計(jì)算邏輯，如求最值等）  所以我們一般看到的狀態(tài)轉(zhuǎn)移方程，基本都是這樣：
每一個(gè)狀態(tài)轉(zhuǎn)移方程，多少都有一些細(xì)微的差別。這個(gè)其實(shí)很容易理解，世間的關(guān)系多了去了，不可能抽象出完全可以套用的公式。所以我個(gè)人其實(shí)不建議去死記硬背各種類型的狀態(tài)轉(zhuǎn)移方程。但是DP的題型真的就完全無法掌握，無法歸類進(jìn)行分析嗎？我認(rèn)為不是的。在本系列中，我將由簡入深為大家講解動(dòng)態(tài)規(guī)劃這個(gè)主題。 我們先看上一道最簡單的DP題目，熟悉DP的概念： 題目：假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？注意：給定 n 是一個(gè)正整數(shù)。
1.2 題目圖解通過分析我們可以明確，該題可以被分解為一些包含最優(yōu)子結(jié)構(gòu)的子問題，即它的最優(yōu)解可以從其子問題的最優(yōu)解來有效地構(gòu)建。滿足“將大問題分解為若干個(gè)規(guī)模較小的問題”的條件。所以我們令 dp[n] 表示能到達(dá)第 n 階的方法總數(shù)，可以得到如下狀態(tài)轉(zhuǎn)移方程：
 1.3 Go語言示例根據(jù)分析，得到代碼如下： func climbStairs(n int) int { if n == 1 { return 1 } dp := make([]int, n+1) dp[1] = 1 dp[2] = 2 for i := 3; i <= n; i++ { dp[i] = dp[i-1] + dp[i-2] } return dp[n]}動(dòng)態(tài)規(guī)劃系列二：最大子序和2.1 最大子序和題目：給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
拿到題目請(qǐng)不要看下方題解，先自行思考2-3分鐘.... 2.2 題目圖解首先我們分析題目，一個(gè)連續(xù)子數(shù)組一定要以一個(gè)數(shù)作為結(jié)尾，那么我們可以將狀態(tài)定義成如下：
那么為什么這么定義呢？因?yàn)檫@樣定義其實(shí)是最容易想到的！在上一節(jié)中我們提到，狀態(tài)轉(zhuǎn)移方程其實(shí)是通過1-3個(gè)參數(shù)的方程來描述小規(guī)模問題和大規(guī)模問題間的關(guān)系。 當(dāng)然，如果你沒有想到，其實(shí)也非常正常！因?yàn)?'該問題最早于 1977 年提出，但是直到 1984 年才被發(fā)現(xiàn)了線性時(shí)間的最優(yōu)解法。' 根據(jù)狀態(tài)的定義，我們繼續(xù)進(jìn)行分析： 如果要得到dp[i]，那么nums[i]一定會(huì)被選取。并且 dp[i] 所表示的連續(xù)子序列與 dp[i-1] 所表示的連續(xù)子序列很可能就差一個(gè) nums[i] 。即
但是這里我們遇到一個(gè)問題，很有可能dp[i-1]本身是一個(gè)負(fù)數(shù)。那這種情況的話，如果dp[i]通過dp[i-1]+nums[i]來推導(dǎo)，那么結(jié)果其實(shí)反而變小了，因?yàn)槲覀僤p[i]要求的是最大和。所以在這種情況下，如果dp[i-1]<0，那么dp[i]其實(shí)就是nums[i]的值。即
綜上分析，我們可以得到：
得到了狀態(tài)轉(zhuǎn)移方程，但是我們還需要通過一個(gè)已有的狀態(tài)的進(jìn)行推導(dǎo)，我們可以想到 dp[0] 一定是以 nums[0] 進(jìn)行結(jié)尾，所以
在很多題目中，因?yàn)閐p[i]本身就定義成了題目中的問題，所以dp[i]最終就是要的答案。但是這里狀態(tài)中的定義，并不是題目中要的問題，不能直接返回最后的一個(gè)狀態(tài) (這一步經(jīng)常有初學(xué)者會(huì)摔跟頭)。所以最終的答案，其實(shí)我們是尋找：
分析完畢，我們繪制成圖： 假定 nums 為 [-2,1,-3,4,-1,2,1,-5,4]  2.3 Go語言示例根據(jù)分析，得到代碼如下： 我們可以進(jìn)一步精簡代碼為： func maxSubArray(nums []int) int { if len(nums) < 1 { return 0 } dp := make([]int, len(nums)) result := nums[0] dp[0] = nums[0] for i := 1; i < len(nums); i++ { dp[i] = max(dp[i-1]+nums[i], nums[i]) result = max(dp[i], result) } return result}func max(a, b int) int { if a > b { return a } return b}復(fù)雜度分析：時(shí)間復(fù)雜度：O(N)?？臻g復(fù)雜度：O(N)。 動(dòng)態(tài)規(guī)劃系列三：最長上升子序列3.1 最長上升子序列題目：給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
本題有一定難度！ 如果沒有思路請(qǐng)回顧上一篇的學(xué)習(xí)內(nèi)容！ 不建議直接看題解！ 3.2 題目圖解首先我們分析題目，要找的是最長上升子序列（Longest Increasing Subsequence，LIS）。因?yàn)轭}目中沒有要求連續(xù)，所以LIS可能是連續(xù)的，也可能是非連續(xù)的。同時(shí)，LIS符合可以從其子問題的最優(yōu)解來進(jìn)行構(gòu)建的條件。所以我們可以嘗試用動(dòng)態(tài)規(guī)劃來進(jìn)行求解。首先我們定義狀態(tài)：
我們假定nums為[1，9，5，9，3]  我們分兩種情況進(jìn)行討論：
我們先初步得出上面的結(jié)論，但是我們發(fā)現(xiàn)了一些問題。因?yàn)閐p[i]前面比他小的元素，不一定只有一個(gè)！ 可能除了nums[j]，還包括nums[k]，nums[p] 等等等等。所以dp[i]除了可能等于dp[j]+1，還有可能等于dp[k]+1，dp[p]+1 等等等等。所以我們求dp[i]，需要找到dp[j]+1，dp[k]+1，dp[p]+1 等等等等中的最大值。（我在3個(gè)等等等等上都進(jìn)行了加粗，主要是因?yàn)槌鯇W(xué)者非常容易在這里摔跟斗！這里強(qiáng)調(diào)的目的是希望能記住這道題型?。?/p> 即：
最后，我們只需要找到dp數(shù)組中的最大值，就是我們要找的答案。 分析完畢，我們繪制成圖：  3.3 Go語言示例根據(jù)分析，得到代碼如下： 動(dòng)態(tài)規(guī)劃系列四：三角形最小路徑和前面章節(jié)我們通過題目“最長上升子序列”以及'最大子序和'，學(xué)習(xí)了DP（動(dòng)態(tài)規(guī)劃）在線性關(guān)系中的分析方法。這種分析方法，也在運(yùn)籌學(xué)中被稱為“線性動(dòng)態(tài)規(guī)劃”，具體指的是 “目標(biāo)函數(shù)為特定變量的線性函數(shù)，約束是這些變量的線性不等式或等式，目的是求目標(biāo)函數(shù)的最大值或最小值”。這點(diǎn)大家作為了解即可，不需要死記，更不要生搬硬套！ 在本節(jié)中，我們將繼續(xù)分析一道略微區(qū)別于之前的題型，希望可以由此題與之前的題目進(jìn)行對(duì)比論證，進(jìn)而順利求解！ 4.1 三角形最小路徑和題目：給定一個(gè)三角形，找出自頂向下的最小路徑和。
4.2 自頂向下圖解分析首先我們分析題目，要找的是三角形最小路徑和，這是個(gè)啥意思呢？假設(shè)我們有一個(gè)三角形：[[2], [3,4], [6,5,7], [4,1,8,3]]  那從上到下的最小路徑和就是2-3-5-1，等于11。 由于我們是使用數(shù)組來定義一個(gè)三角形，所以便于我們分析，我們將三角形稍微進(jìn)行改動(dòng)：  這樣相當(dāng)于我們將整個(gè)三角形進(jìn)行了拉伸。這時(shí)候，我們根據(jù)題目中給出的條件：每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。其實(shí)也就等同于，每一步我們只能往下移動(dòng)一格或者右下移動(dòng)一格。將其轉(zhuǎn)化成代碼，假如2所在的元素位置為[0,0]，那我們往下移動(dòng)就只能移動(dòng)到[1,0]或者[1,1]的位置上。假如5所在的位置為[2,1]，同樣也只能移動(dòng)到[3,1]和[3,2]的位置上。如下圖所示：  題目明確了之后，現(xiàn)在我們開始進(jìn)行分析。題目很明顯是一個(gè)找最優(yōu)解的問題，并且可以從子問題的最優(yōu)解進(jìn)行構(gòu)建。所以我們通過動(dòng)態(tài)規(guī)劃進(jìn)行求解。首先，我們定義狀態(tài)：
我們很容易想到可以自頂向下進(jìn)行分析。并且，無論最后的路徑是哪一條，它一定要經(jīng)過最頂上的元素，即[0,0]。所以我們需要對(duì)dp[0][0]進(jìn)行初始化。
繼續(xù)分析，如果我們要求dp[i][j]，那么其一定會(huì)從自己頭頂上的兩個(gè)元素移動(dòng)而來。  如5這個(gè)位置的最小路徑和，要么是從2-3-5而來，要么是從2-4-5而來。然后取兩條路徑和中較小的一個(gè)即可。進(jìn)而我們得到狀態(tài)轉(zhuǎn)移方程：
但是，我們這里會(huì)遇到一個(gè)問題！除了最頂上的元素之外，  最左邊的元素只能從自己頭頂而來。（2-3-6-4） 最右邊的元素只能從自己左上角而來。（2-4-7-3） 然后，我們觀察發(fā)現(xiàn)，位于第2行的元素，都是特殊元素（因?yàn)槎贾荒軓腫0,0]的元素走過來） 我們可以直接將其特殊處理，得到：
最后，我們只要找到最后一行元素中，路徑和最小的一個(gè)，就是我們的答案。即：
綜上我們就分析完了，我們總共進(jìn)行了4步：
4.3 代碼分析分析完畢，代碼自成： func minimumTotal(triangle [][]int) int { if len(triangle) < 1 { return 0 } if len(triangle) == 1 { return triangle[0][0] } dp := make([][]int, len(triangle)) for i, arr := range triangle { dp[i] = make([]int, len(arr)) } result := 1<<31 - 1 dp[0][0] = triangle[0][0] dp[1][1] = triangle[1][1] + triangle[0][0] dp[1][0] = triangle[1][0] + triangle[0][0] for i := 2; i < len(triangle); i++ { for j := 0; j < len(triangle[i]); j++ { if j == 0 { dp[i][j] = dp[i-1][j] + triangle[i][j] } else if j == (len(triangle[i]) - 1) { dp[i][j] = dp[i-1][j-1] + triangle[i][j] } else { dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] } } } for _,k := range dp[len(dp)-1] { result = min(result, k) } return result}func min(a, b int) int { if a > b { return b } return a}運(yùn)行上面的代碼，我們發(fā)現(xiàn)使用的內(nèi)存過大。我們有沒有什么辦法可以壓縮內(nèi)存呢？通過觀察我們發(fā)現(xiàn)，在我們自頂向下的過程中，其實(shí)我們只需要使用到上一層中已經(jīng)累積計(jì)算完畢的數(shù)據(jù)，并且不會(huì)再次訪問之前的元素?cái)?shù)據(jù)。繪制成圖如下： 優(yōu)化后的代碼如下： 動(dòng)態(tài)規(guī)劃系列五：最小路徑和在上節(jié)中，我們通過分析，順利完成了“三角形最小路徑和”的動(dòng)態(tài)規(guī)劃題解。在本節(jié)中，我們繼續(xù)看一道相似題型，以求能完全掌握這種“路徑和”的問題。話不多說，先看題目： 5.1 最小路徑和題目：給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。說明：每次只能向下或者向右移動(dòng)一步。
5.2 圖解分析首先我們分析題目，要找的是 最小路徑和，這是個(gè)啥意思呢？假設(shè)我們有一個(gè) m*n 的矩形 ：[[1,3,1],[1,5,1],[4,2,1]] 那從左上角到右下角的最小路徑和，我們可以很容易看出就是1-3-1-1-1，這一條路徑，結(jié)果等于7。 題目明確了，我們繼續(xù)進(jìn)行分析。該題與上一道求三角形最小路徑和一樣，題目明顯符合可以從子問題的最優(yōu)解進(jìn)行構(gòu)建，所以我們考慮使用動(dòng)態(tài)規(guī)劃進(jìn)行求解。首先，我們定義狀態(tài)：
同樣，因?yàn)槿魏我粭l到達(dá)右下角的路徑，都會(huì)經(jīng)過[0,0]這個(gè)元素。所以我們需要對(duì)dp[0][0]進(jìn)行初始化。
繼續(xù)分析，根據(jù)題目給的條件，如果我們要求dp[i][j]，那么它一定是從自己的上方或者左邊移動(dòng)而來。如下圖所示：
進(jìn)而我們得到狀態(tài)轉(zhuǎn)移方程：
同樣我們需要考慮兩種特殊情況：
最后，因?yàn)槲覀兊哪繕?biāo)是從左上角走到右下角，整個(gè)網(wǎng)格的最小路徑和其實(shí)就是包含右下角元素的最小路徑和。即：
綜上我們就分析完了，我們總共進(jìn)行了4步：
5.3 代碼分析分析完畢，代碼自成： func minPathSum(grid [][]int) int { l := len(grid) if l < 1 { return 0 } dp := make([][]int, l) for i, arr := range grid { dp[i] = make([]int, len(arr)) } dp[0][0] = grid[0][0] for i := 0; i < l; i++ { for j := 0; j < len(grid[i]); j++ { if i == 0 && j != 0 { dp[i][j] = dp[i][j-1] + grid[i][j] } else if j == 0 && i != 0 { dp[i][j] = dp[i-1][j] + grid[i][j] } else if i != 0 && j != 0 { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] } } } return dp[l-1][len(dp[l-1])-1]}func min(a, b int) int { if a > b { return b } return a}同樣，運(yùn)行上面的代碼，我們發(fā)現(xiàn)使用的內(nèi)存過大。有沒有什么辦法可以壓縮內(nèi)存呢？通過觀察我們發(fā)現(xiàn)，在我們自左上角到右下角計(jì)算各個(gè)節(jié)點(diǎn)的最小路徑和的過程中，我們只需要使用到之前已經(jīng)累積計(jì)算完畢的數(shù)據(jù)，并且不會(huì)再次訪問之前的元素?cái)?shù)據(jù)。繪制成圖如下：(大家看這個(gè)過程像不像掃雷，其實(shí)如果大家研究掃雷外掛的話，就會(huì)發(fā)現(xiàn)在掃雷的核心算法中，就有一處頗為類似這種分析方法，這里就不深究了) 優(yōu)化后的代碼如下：
|
|
|
