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