|
今天是小浩算法 “365刷題計(jì)劃” 動(dòng)態(tài)規(guī)劃 - 整合篇,。大家應(yīng)該期待已久了吧！奧利給,！ 01 PART 動(dòng)態(tài)規(guī)劃是啥 我們把要解決的一個(gè)大問(wèn)題轉(zhuǎn)換成若干個(gè)規(guī)模較小的同類型問(wèn)題,，當(dāng)我們求解出這些小問(wèn)題的答案，大問(wèn)題便不攻自破,。同時(shí),，在求解這些小問(wèn)題的過(guò)程中，我們把需要重復(fù)計(jì)算的答案記錄下來(lái)放在數(shù)組中,，下次如果遇到同樣的小問(wèn)題需要計(jì)算,，便直接查詢出結(jié)果。這就是動(dòng)態(tài)規(guī)劃,。 很多人覺(jué)得DP難（下文統(tǒng)稱動(dòng)態(tài)規(guī)劃為DP）,，根本原因是因?yàn)镈P區(qū)別于一些固定形式的算法（如 DFS、二分法,、KMP）,，沒(méi)有固定的步驟規(guī)定第一步第二步來(lái)做什么。所以我覺(jué)得DP更應(yīng)該被看作為一種解決問(wèn)題的思想,。這種思想的本質(zhì)是：一個(gè)規(guī)模較大的問(wèn)題（可以用兩三個(gè)參數(shù)表示）,，通過(guò)若干規(guī)模較小的問(wèn)題的結(jié)果來(lái)得到的（通常會(huì)尋求到一些特殊的計(jì)算邏輯,，如求最值等） 講解動(dòng)態(tài)規(guī)劃的資料很多，官方的定義是指把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題,，利用各階段之間的關(guān)系,，逐個(gè)求解。概念中的各階段之間的關(guān)系,，其實(shí)指的就是狀態(tài)轉(zhuǎn)移方程,。 我們一般看到的狀態(tài)轉(zhuǎn)移方程，基本長(zhǎng)成下面這樣（注：i,、j、k 都是在定義DP方程中用到的參數(shù),。opt 指代特殊的計(jì)算邏輯,，大多數(shù)情況下為 max 或 min。func 指代邏輯函數(shù)）：
到這里估計(jì)大家要懵逼了,，這特么都是些啥玩意,。先別著急叉掉這個(gè)頁(yè)面，聽我慢慢說(shuō)來(lái),。狀態(tài)轉(zhuǎn)移方程,，說(shuō)白了是用來(lái)描述大規(guī)模問(wèn)題和小規(guī)模問(wèn)題之間的關(guān)系。既然是關(guān)系,，那肯定就不是唯一的,，抽象的，形式化的東西,?？梢杂眯∧粗赶胂耄澜缟详P(guān)系那么多,，你怎么可能全部能記得住,。所以我個(gè)人并不建議去死記硬背各種類型的狀態(tài)轉(zhuǎn)移方程。脫離了應(yīng)用場(chǎng)景的公式,，全部都是耍流氓,，生搬硬套的結(jié)果一定是四不像。既然如此,，那DP的題型就完全無(wú)法掌握嗎,？我認(rèn)為不是。在本節(jié)中,，我們將通過(guò)5道題目,，帶著大家由淺入深學(xué)習(xí)一下動(dòng)態(tài)規(guī)劃的核心思想。 02 PART 爬樓梯 我們先通過(guò)一道最簡(jiǎn)單的DP題目,，熟悉DP的概念,。 第70題：假設(shè)你正在爬樓梯,。需要 n 階你才能到達(dá)樓頂。每次你可以爬 1 或 2 個(gè)臺(tái)階,。你有多少種不同的方法可以爬到樓頂呢,？ 注意：給定 n 是一個(gè)正整數(shù)。 示例 1： 輸入：2 輸出：2 解釋：有兩種方法可以爬到樓頂,。1. 1 階 + 1 階2. 2 階 示例 2： 輸入：3 輸出：3 解釋：有三種方法可以爬到樓頂,。1. 1 階 + 1 階 + 1 階2. 1 階 + 2 階3. 2 階 + 1 階 首先我們分析本題，該題滿足“大問(wèn)題由小問(wèn)題的結(jié)果產(chǎn)生”的條件：
“大問(wèn)題由小問(wèn)題的結(jié)果產(chǎn)生”,，我們也可以換個(gè)專業(yè)點(diǎn)的說(shuō)法：即該問(wèn)題的最優(yōu)解可以從其子問(wèn)題的最優(yōu)解來(lái)進(jìn)行構(gòu)建。我們令 dp[n] 表示到達(dá)第 n 階的方法總數(shù),。可以得到如下狀態(tài)轉(zhuǎn)移方程(如果不明白,，可以認(rèn)真看一下上面的圖)：
根據(jù)分析，得出代碼：（Go語(yǔ)言） 1func climbStairs(n int) int {2 if n == 1 {3 return 14 }5 dp := make([]int, n+1)6 dp[1] = 17 dp[2] = 28 for i := 3; i <= n; i++ {9 dp[i] = dp[i-1] + dp[i-2]10 }11 return dp[n]12}
03 PART 最大子序和 在上文中,，我們講解了DP的概念并且通過(guò)示例進(jìn)行了學(xué)習(xí)?，F(xiàn)在我們繼續(xù)通過(guò)一道簡(jiǎn)單例題，來(lái)加強(qiáng)大家的理解,。 第53題：給定一個(gè)整數(shù)數(shù)組 nums ,，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和,。 示例: 輸入: [-2,1,-3,4,-1,2,1,-5,4], 輸出: 6 解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大,，為 6。 動(dòng)態(tài)規(guī)劃第一步：定義狀態(tài),。對(duì)于本題如何定義狀態(tài),？我們分析題目，一個(gè)連續(xù)子數(shù)組一定要以一個(gè)數(shù)作為結(jié)尾,，那是不是可以定義dp[i] 表示以 nums[i] 結(jié)尾的連續(xù)子數(shù)組的最大和,。為啥要這樣定義？如果要得到dp[i],，那么nums[i]一定會(huì)被選取,。并且 dp[i] 所表示的連續(xù)子序列與 dp[i-1] 所表示的連續(xù)子序列很可能就差一個(gè) nums[i]，當(dāng)然這是在dp[i-1]大于0的情況下,。公式是這樣： dp[i] = dp[i-1]+nums[i] , if (dp[i-1] >= 0) 自然,，dp[i-1]也是有可能小于0的，此時(shí)dp[i]的值就是nums[i]了,。 dp[i] = nums[i] , if (dp[i-1] < 0) 通過(guò)上面的分析,，我們可以得出狀態(tài)轉(zhuǎn)移方程： dp[i]=max(nums[i], dp[i?1]+nums[i]) 得到了狀態(tài)轉(zhuǎn)移方程,，但是我們還需要通過(guò)一個(gè)已有的狀態(tài)的進(jìn)行推導(dǎo)，我們可以想到 dp[0] 一定是以 nums[0] 進(jìn)行結(jié)尾,。所以對(duì)dp[0]進(jìn)行初始化： dp[0] = nums[0] 問(wèn)題來(lái)了,，最終的答案是啥？在很多題目中,，因?yàn)閐p[i]本身就定義成了題目中的問(wèn)題,，所以dp[i]最終就是要的答案。但是對(duì)于本題,，這里定義的狀態(tài),，并不是題目中要求解的問(wèn)題，所以不能直接返回最后的一個(gè)狀態(tài) (這一步經(jīng)常有初學(xué)者會(huì)摔跟頭),。那最終答案是啥呢,？其實(shí)我們是尋找： max(dp[0], dp[1], ..., d[i-1], dp[i]) 干巴巴的說(shuō)了半天，我們繪制成圖可能更容易理解： 根據(jù)分析,，得出代碼： 1func maxSubArray(nums []int) int {2 if len(nums) < 1 {3 return 04 }5 dp := make([]int, len(nums))6 //設(shè)置初始化值 7 dp[0] = nums[0]8 for i := 1; i < len(nums); i++ {9 //處理 dp[i-1] < 0 的情況10 if dp[i-1] < 0 {11 dp[i] = nums[i]12 } else {13 dp[i] = dp[i-1] + nums[i]14 }15 }16 result := -1 << 3117 for _, k := range dp {18 result = max(result, k)19 }20 return result21}2223func max(a, b int) int {24 if a > b {25 return a26 }27 return b28}
進(jìn)一步精簡(jiǎn)代碼： 1func maxSubArray(nums []int) int {2 if len(nums) < 1 {3 return 04 }5 dp := make([]int, len(nums))6 result := nums[0]7 dp[0] = nums[0]8 for i := 1; i < len(nums); i++ {9 dp[i] = max(dp[i-1]+nums[i], nums[i])10 result = max(dp[i], result)11 }12 return result13}1415func max(a, b int) int {16 if a > b {17 return a18 }19 return b20}
這個(gè)例子是為了告訴大家：狀態(tài)的定義并不一定是最終求解的問(wèn)題答案，自然也就不能想當(dāng)然的到最后返回一個(gè)dp[i]就覺(jué)得完事,，具體問(wèn)題具體分析,，把握住狀態(tài)的含義才是核心。（謹(jǐn)記） 04 PART 最長(zhǎng)上升子序列 前面兩道題,，相信大家對(duì)DP已不陌生,，本題將增加一定難度。（越短越難有木有） 第300題：給定一個(gè)無(wú)序的整數(shù)數(shù)組,，找到其中最長(zhǎng)上升子序列的長(zhǎng)度,。 示例: 輸入: [10,9,2,5,3,7,101,18] 輸出: 4 解釋: 最長(zhǎng)的上升子序列是 [2,3,7,101]，它的長(zhǎng)度是 4,。 說(shuō)明: 可能會(huì)有多種最長(zhǎng)上升子序列的組合,，你只需要輸出對(duì)應(yīng)的長(zhǎng)度即可。 首先我們分析題目,，要找的是最長(zhǎng)上升子序列（Longest Increasing Subsequence,，LIS）。因?yàn)轭}目中沒(méi)有要求連續(xù),，所以LIS可能是連續(xù)的,，也可能是非連續(xù)的。同時(shí),，LIS符合可以從其子問(wèn)題的最優(yōu)解來(lái)進(jìn)行構(gòu)建的條件,。所以我們可以嘗試用動(dòng)態(tài)規(guī)劃來(lái)進(jìn)行求解。首先我們定義狀態(tài)：dp[i] 表示以nums[i]結(jié)尾的最長(zhǎng)上升子序列的長(zhǎng)度,。我們假定nums為[1,，9,，5，9,，3]： 我們初步可以得到下面的結(jié)論：
為什么第二個(gè)結(jié)論錯(cuò)誤？因?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 等等等等 中的最大值。（初學(xué)者極易在這里摔跟頭）我們可以得到下面的狀態(tài)轉(zhuǎn)移公式： dp[i] = max(dp[j]+1,，dp[k]+1,，dp[p]+1，.....) 條件： nums[i] > nums[j] nums[i] > nums[k] nums[i] > nums[p] 如果不能理解,，可以看下面這個(gè)圖：
最后我們只需要找DP數(shù)組中的最大值即可,，代碼如下： 1func lengthOfLIS(nums []int) int {2 if len(nums) < 1 {3 return 04 }5 dp := make([]int, len(nums))6 result := 17 for i := 0; i < len(nums); i++ {8 dp[i] = 19 for j := 0; j < i; j++ {10 //這行代碼就是上文中那個(gè) 等等等等11 if nums[j] < nums[i] {12 dp[i] = max(dp[j]+1, dp[i])13 }14 }15 result = max(result, dp[i])16 }17 return result18}1920func max(a, b int) int {21 if a > b {22 return a23 }24 return b25}
這道題目相比上面兩道題難度有所提升，但其解題思想與上面兩題如出一轍,，請(qǐng)大家認(rèn)真思考,。 05 PART 三角形最小路徑和
在上文中，我們通過(guò)題目“最長(zhǎng)上升子序列”以及"最大子序和",，學(xué)習(xí)了DP在線性關(guān)系中的分析方法,。這種分析方法，在運(yùn)籌學(xué)中也被稱為“線性動(dòng)態(tài)規(guī)劃”,，當(dāng)然這點(diǎn)大家作為了解即可?，F(xiàn)在我們將分享一道略微區(qū)別于前面三道題的類型。 第120題：給定一個(gè)三角形,，找出自頂向下的最小路徑和,。 每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。 例如，給定三角形： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自頂向下的最小路徑和為 11（即,，2 + 3 + 5 + 1 = 11）,。 不少人在這道題目上栽過(guò)跟頭，一起分析一下,。首先我們要找的是三角形最小路徑和,，總得知道這是個(gè)啥意思。假設(shè)我們有一個(gè)三角形：[[2], [3,4], [6,5,7], [4,1,8,3]],，長(zhǎng)這樣：
那從上到下的最小路徑和就是2-3-5-1,，等于11。由于我們是使用數(shù)組來(lái)定義一個(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]的位置上。如下圖所示：
明確了題目,，我們開始分析。題目很明顯滿足可以從子問(wèn)題的最優(yōu)解進(jìn)行構(gòu)建的條件,，所以我們考慮通過(guò)動(dòng)態(tài)規(guī)劃進(jìn)行求解,。老樣子，我們先定義狀態(tài)： dp[i][j] : 表示包含第i行j列元素的最小路徑和 我們很容易想到可以自頂向下進(jìn)行分析,。并且,，無(wú)論最后的路徑是哪一條，它一定要經(jīng)過(guò)最頂上的元素,，即[0,0],。所以我們需要對(duì)dp[0][0]進(jìn)行初始化。 dp[0][0] = [0][0]位置所在的元素值 繼續(xù)分析,，如果我們要求dp[i][j],，那么其一定會(huì)從自己頭頂上的兩個(gè)元素移動(dòng)而來(lái)。啥意思：
如5這個(gè)位置的最小路徑和,，要么是從2-3-5而來(lái),，要么是從2-4-5而來(lái)。然后取兩條路徑和中較小的一個(gè)即可。進(jìn)而我們得到狀態(tài)轉(zhuǎn)移方程： dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j] 但是,，我們這里會(huì)遇到一個(gè)問(wèn)題,！除了最頂上的元素之外，
最左邊的元素只能從自己頭頂而來(lái),。（2-3-6-4）
最右邊的元素只能從自己左上角而來(lái),。（2-4-7-3） 同時(shí)，我們觀察到,，位于第2行的元素,，都是特殊元素（因?yàn)槎贾荒軓腫0,0]的元素走過(guò)來(lái)），我們可以直接將其特殊處理,，得到： dp[1][0] = triangle[1][0] + triangle[0][0] dp[1][1] = triangle[1][1] + triangle[0][0] 最后,，我們只要找到最后一行元素中，路徑和最小的一個(gè),，就是我們的答案,。即（l為dp數(shù)組長(zhǎng)度）： result = min(dp[l-1,0]，dp[l-1,1],，dp[l-1,2]....) 綜上我們就分析完了,，我們總共進(jìn)行了4步：
根據(jù)分析,，得出代碼： 1//未優(yōu)化內(nèi)存版本2func minimumTotal(triangle [][]int) int {3 if len(triangle) < 1 {4 return 05 }6 if len(triangle) == 1 {7 return triangle[0][0]8 }9 dp := make([][]int, len(triangle))10 for i, arr := range triangle {11 dp[i] = make([]int, len(arr))12 }1314 result := 2 << 31 + 115 dp[0][0] = triangle[0][0]16 dp[1][1] = triangle[1][1] + triangle[0][0]17 dp[1][0] = triangle[1][0] + triangle[0][0]1819 for i := 2; i < len(triangle); i++ {20 for j := 0; j < len(triangle[i]); j++ {21 if j == 0 {22 dp[i][j] = dp[i-1][j] + triangle[i][j]23 } else if j == (len(triangle[i]) - 1) {24 dp[i][j] = dp[i-1][j-1] + triangle[i][j]25 } else {26 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]27 }28 } 29 }30 for _,k := range dp[len(dp)-1] {31 result = min(result, k)32 }33 return result34}3536func min(a, b int) int {37 if a > b {38 return b39 }40 return a41}
運(yùn)行上面的代碼,，我們發(fā)現(xiàn)使用的內(nèi)存過(guò)大。我們有沒(méi)有什么辦法可以壓縮內(nèi)存呢,？通過(guò)觀察我們發(fā)現(xiàn),，在我們自頂向下的過(guò)程中，其實(shí)我們只需要使用到上一層中已經(jīng)累積計(jì)算完畢的數(shù)據(jù),，并且不會(huì)再次訪問(wèn)之前的元素?cái)?shù)據(jù),。繪制成圖如下：
所以我們可以優(yōu)化代碼： 1//優(yōu)化版本2func minimumTotal(triangle [][]int) int {3 l := len(triangle)4 if l < 1 {5 return 06 }7 if l == 1 {8 return triangle[0][0]9 }10 result := 1<<31 - 111 triangle[0][0] = triangle[0][0]12 triangle[1][1] = triangle[1][1] + triangle[0][0]13 triangle[1][0] = triangle[1][0] + triangle[0][0]14 for i := 2; i < l; i++ {15 for j := 0; j < len(triangle[i]); j++ {16 if j == 0 {17 triangle[i][j] = triangle[i-1][j] + triangle[i][j]18 } else if j == (len(triangle[i]) - 1) {19 triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]20 } else {21 triangle[i][j] = min(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]22 }23 } 24 }25 for _,k := range triangle[l-1] {26 result = min(result, k)27 }28 return result29}3031func min(a, b int) int {32 if a > b {33 return b34 }35 return a36}
可以看到現(xiàn)在內(nèi)存極大的進(jìn)行了優(yōu)化?？偨Y(jié)一下,，這道題的難度是比前面幾道題大的，但是還是可以按部就班的進(jìn)行分析,。當(dāng)然,，在分析的過(guò)程中，本題我們引入了一個(gè)技巧：根據(jù)每次計(jì)算只會(huì)訪問(wèn)前一次計(jì)算結(jié)果的特性,，我們把原數(shù)組直接當(dāng)成了DP數(shù)組來(lái)進(jìn)行使用,。（同時(shí)，本題其實(shí)還可以自下而上進(jìn)行分析,，大家可以下去嘗試一下） 06 PART 最小路徑和
在上文中,，我們通過(guò)分析,，順利完成了“三角形最小路徑和”的動(dòng)態(tài)規(guī)劃題解。在本節(jié)中,，我們繼續(xù)看一道相似題型,，以求能完全掌握這種“路徑和”問(wèn)題。 第64題：給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格,，請(qǐng)找出一條從左上角到右下角的路徑,，使得路徑上的數(shù)字總和為最小。 說(shuō)明：每次只能向下或者向右移動(dòng)一步,。 示例: 輸入: [ [1,3,1], [1,5,1], [4,2,1] ] 輸出: 7 解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小,。 上一題是三角形，這一道題換成了矩形,，是不是可以直接“抄”上面的分析過(guò)程呢,？分析一下，要找的是 最小路徑和,，這是個(gè)啥意思呢,？假設(shè)我們有一個(gè) m*n 的矩形 ：[[1,3,1],[1,5,1],[4,2,1]]
那從左上角到右下角的最小路徑和，我們可以很容易看出就是1-3-1-1-1,，這一條路徑,，結(jié)果等于7。 明確題目后繼續(xù)分析,，該題與上一道求三角形最小路徑和一樣,，題目符合可以從子問(wèn)題的最優(yōu)解進(jìn)行構(gòu)建，所以我們考慮使用動(dòng)態(tài)規(guī)劃進(jìn)行求解,。首先,，我們定義狀態(tài)： dp[i][j] : 表示包含第i行j列元素的最小路徑和 同樣，因?yàn)槿魏我粭l到達(dá)右下角的路徑,，都會(huì)經(jīng)過(guò)[0,0]這個(gè)元素,。所以我們需要對(duì)dp[0][0]進(jìn)行初始化。 dp[0][0] = [0][0]位置所在的元素值 繼續(xù)分析,，根據(jù)題目給的條件，如果我們要求dp[i][j],，那么它一定是從自己的上方或者左邊移動(dòng)而來(lái),。如下圖所示：
5，只能從3或者1移動(dòng)而來(lái) 2,，只能從5或者4移動(dòng)而來(lái) 4,，從1移動(dòng)而來(lái) 3，從1移動(dòng)而來(lái) （紅色位置必須從藍(lán)色位置移動(dòng)而來(lái)） 進(jìn)而我們得到狀態(tài)轉(zhuǎn)移方程： dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j] 同樣我們需要考慮兩種特殊情況：
最后，因?yàn)槲覀兊哪繕?biāo)是從左上角走到右下角，整個(gè)網(wǎng)格的最小路徑和其實(shí)就是包含右下角元素的最小路徑和,。即： 設(shè)：dp的長(zhǎng)度為l 最終結(jié)果就是：dp[l-1][len(dp[l-1])-1] 綜上我們就分析完了,，我們總共進(jìn)行了4步：
根據(jù)分析,，得出題解： 1//原始版本2func minPathSum(grid [][]int) int {3 l := len(grid)4 if l < 1 {5 return 06 }7 dp := make([][]int, l)8 for i, arr := range grid {9 dp[i] = make([]int, len(arr))10 }11 dp[0][0] = grid[0][0]12 for i := 0; i < l; i++ {13 for j := 0; j < len(grid[i]); j++ {14 if i == 0 && j != 0 {15 dp[i][j] = dp[i][j-1] + grid[i][j]16 } else if j == 0 && i != 0 {17 dp[i][j] = dp[i-1][j] + grid[i][j]18 } else if i !=0 && j != 0 {19 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]20 }21 }22 }23 return dp[l-1][len(dp[l-1])-1]24}2526func min(a, b int) int {27 if a > b {28 return b29 }30 return a31}
事實(shí)總是驚人的相似,，運(yùn)行上面的代碼，內(nèi)存又過(guò)大了,。有沒(méi)有什么辦法可以壓縮內(nèi)存呢,？同樣的方法，在我們自左上角到右下角計(jì)算各個(gè)節(jié)點(diǎn)的最小路徑和的過(guò)程中,，我們只需要使用到之前已經(jīng)累積計(jì)算完畢的數(shù)據(jù),，并且不會(huì)再次訪問(wèn)之前的元素?cái)?shù)據(jù)。繪制成圖如下：
優(yōu)化后的代碼如下： 1//優(yōu)化版本2func minPathSum(grid [][]int) int {3 l := len(grid)4 if l < 1 {5 return 06 }7 for i := 0; i < l; i++ {8 for j := 0; j < len(grid[i]); j++ {9 if i == 0 && j != 0 {10 grid[i][j] = grid[i][j-1] + grid[i][j]11 } else if j == 0 && i != 0 {12 grid[i][j] = grid[i-1][j] + grid[i][j]13 } else if i !=0 && j != 0 {14 grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]15 }16 }17 }18 return grid[l-1][len(grid[l-1])-1]19}2021func min(a, b int) int {22 if a > b {23 return b24 }25 return a26}
07 PART 打家劫舍
通過(guò)上文的學(xué)習(xí),，相信大家已經(jīng)對(duì)DP有所了解,。這道題將回歸一道簡(jiǎn)單問(wèn)題，和大家探究一個(gè)疑惑：如果狀態(tài)定義出錯(cuò),，會(huì)出現(xiàn)什么問(wèn)題,？ 第198題：你是一個(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 ,。 上面的題目，我們第一步都是先定義狀態(tài),。只要定義好了狀態(tài),，同時(shí)分析出狀態(tài)轉(zhuǎn)移方程，一般就可以流暢的解決問(wèn)題了,。但是如果狀態(tài)定義出錯(cuò)會(huì)發(fā)生什么呢,？我們嘗試一下：假設(shè)有i間房子,，我們可能會(huì)定義出兩種狀態(tài)：
如果我們定義為狀態(tài)一,，因?yàn)槲覀儧](méi)辦法知道獲取最高金額時(shí)，小偷到底偷盜了哪些房屋,。所以我們需要找到所有狀態(tài)中的最大值,，才能找到我們的最終答案。即： max(dp[0],dp[1],.....,dp[len(dp)-1]) 如果我們定義為狀態(tài)二,，因?yàn)樾⊥狄欢〞?huì)從前偷到最后（強(qiáng)調(diào)：偷盜至第i個(gè)房間,，不代表小偷要從第i個(gè)房間中獲取財(cái)物）。所以我們的最終答案很容易確定,。即： dp[i] 現(xiàn)在我們分析這兩種狀態(tài)定義下的狀態(tài)轉(zhuǎn)移方程： 如果是狀態(tài)一,，偷盜含第i個(gè)房間時(shí)能獲取的最高金額，我們相當(dāng)于要找到偷盜每一間房子時(shí)可以獲取到的最大金額,。比如下圖,，我們要找到dp[4]，也就是偷盜9這間房子時(shí),，能獲取到的最大金額,。
那我們就需要找到與9不相鄰的前后兩段中能獲取到的最大金額。
我們發(fā)現(xiàn)題目進(jìn)入惡性循環(huán),，因?yàn)槲覀內(nèi)粢业脚c9不相鄰的兩端中能偷盜的最大金額,，根據(jù)dp[i]的定義，我們就又需要分析在這兩段中盜取每一間房子時(shí)所能獲取的最大利益,！想想都很可怕,！所以我們放棄掉這種狀態(tài)的定義。 如果是狀態(tài)二,，偷盜至第i個(gè)房子時(shí),，所能獲取的最大利益。那我們可以想到,，由于不可以在相鄰的房屋闖入,，所以 至i房屋可盜竊的最大值，要么就是至 i-1 房屋可盜竊的最大值,，要么就是至 i-2 房屋可盜竊的最大值加上當(dāng)前房屋的值,，二者之間取最大值。即： dp[i] = max(dp[i-2]+nums[i], dp[i-1]) 如果不能理解可以看下圖： （相當(dāng)于小賊背了個(gè)背包,，里邊裝了之前偷來(lái)的財(cái)物,，每到達(dá)下一個(gè)房間門口,，來(lái)選擇是偷還是不偷,。）
1func rob(nums []int) int {2 if len(nums) < 1 {3 return 04 }5 if len(nums) == 1 {6 return nums[0]7 }8 if len(nums) == 2 {9 return max(nums[0],nums[1])10 }11 dp := make([]int, len(nums))12 dp[0] = nums[0]13 dp[1] = max(nums[0],nums[1])14 for i := 2; i < len(nums); i++ {15 dp[i] = max(dp[i-2]+nums[i],dp[i-1])16 }17 return dp[len(dp)-1]18}1920func max(a,b int) int {21 if a > b {22 return a23 }24 return b25}
內(nèi)存又大了,？還是一樣優(yōu)化方法，小賊偷盜的過(guò)程中,，不可能轉(zhuǎn)回頭去到自己已經(jīng)偷過(guò)的房間?。ㄌ溃┬⊥抵恍枰看螌⒇?cái)物搬到下一個(gè)房間就行！ 根據(jù)上面思路,，優(yōu)化后的代碼如下： 1func rob(nums []int) int {2 if len(nums) < 1 {3 return 04 }5 if len(nums) == 1 {6 return nums[0]7 }8 if len(nums) == 2 {9 return max(nums[0],nums[1])10 }11 nums[1] = max(nums[0],nums[1])12 for i := 2; i < len(nums); i++ {13 nums[i] = max(nums[i-2]+nums[i],nums[i-1])14 }15 return nums[len(nums)-1]16}1718func max(a,b int) int {19 if a > b {20 return a21 }22 return b23}
08 PART 啰嗦一下
動(dòng)態(tài)規(guī)劃入門整合系列篇到這里就完事了,，相信大家如果可以完整看完，一定會(huì)有所收獲,。但是呢,，其實(shí)大家可以看到，上面的系列還有很多內(nèi)容沒(méi)有講：比如狀態(tài)壓縮,，背包問(wèn)題 等等,。后面我的計(jì)劃是單獨(dú)拎出來(lái)一個(gè) 背包系列篇 以及 動(dòng)態(tài)規(guī)劃高級(jí)篇系列。 |
|
|
