LeetCode之動(dòng)態(tài)規(guī)劃

　　Easy難度

　　Easy難度的都是一維DP，前面幾道都是我們?cè)趯W(xué)習(xí)dp的時(shí)候經(jīng)常會(huì)遇到的例題。我認(rèn)為dp的關(guān)鍵在于最優(yōu)子結(jié)構(gòu)的選擇，最優(yōu)子結(jié)構(gòu)選擇好了對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移就可以很容易的求解。建議把一些常用的最優(yōu)子結(jié)構(gòu)背下來(lái)(就跟當(dāng)初背快排一樣)，遇到類(lèi)似的題目直接套用或者改變就好了。我的dp解題思路為 確定使用動(dòng)態(tài)規(guī)劃->確定最優(yōu)子結(jié)構(gòu)->確定狀態(tài)轉(zhuǎn)移方程->確定邊界條件。動(dòng)態(tài)規(guī)劃并不是一種具體的解題方法，沒(méi)有萬(wàn)能的公式可以套，而是一種解題的思維方法。

　　53. 最大子序和

　　分析：對(duì)于包含負(fù)數(shù)的求和容易陷入局部最優(yōu)解而忽略全局最優(yōu)解。

　　最優(yōu)子結(jié)構(gòu)：假設(shè)dp[i]表示以j結(jié)尾的最大子序列，也可以假設(shè)dp[i,j]為以i為起點(diǎn)j為終點(diǎn)的最大子序和，這種子結(jié)構(gòu)明顯比第一種復(fù)雜。

　　狀態(tài)轉(zhuǎn)移方程：最優(yōu)子結(jié)構(gòu)確定后可以確定狀態(tài)轉(zhuǎn)移方程了，假設(shè)i-1時(shí)的sum為正數(shù)，那么以i結(jié)尾的子序和為dp[i-1] + nums[i];如果當(dāng)前sum為負(fù)數(shù)，那么不論nums[i]是正是負(fù)，加上一個(gè)負(fù)數(shù)之后都會(huì)減小，直接不加就完事了。因此狀態(tài)轉(zhuǎn)移方程為：dp[i]=max(dp[i-1] + nums[i], nums[i])

　　class Solution:

　　def maxSubArray(self, nums: List[int]) -> int:

　　dp = []

　　for i in range(len(nums)):

　　if i == 0:

　　dp.append(nums[i])

　　else:

　　dp.append(max(dp[i-1] + nums[i], nums[i]))

　　return max(dp)

　　70. 爬樓梯

　　分析: 一維dp還有一種簡(jiǎn)單的解法就是采用數(shù)學(xué)歸納法，首先計(jì)算前幾項(xiàng)，然后歸納出一個(gè)一般通項(xiàng)。這里不需要嚴(yán)格證明，一般歸納的結(jié)果都是正確的，這里用這種方法作為解法。

　　最優(yōu)子結(jié)構(gòu)：對(duì)于一級(jí)臺(tái)階i，最后一步可能有兩種情況，即從i-1上來(lái)，或者從i-2上來(lái)。

　　狀態(tài)轉(zhuǎn)移方程：采用數(shù)學(xué)歸納法：假設(shè)臺(tái)階數(shù)為n，方法數(shù)為dp

　　n = 1, dp[1] = 1

　　n = 2, dp[2] = 2

　　n = 3, dp[3] = 3 (111,12, 21)

　　n = 4, dp[4] = 5 (1111,121,211,112, 22)

　　容易發(fā)現(xiàn) dp[i] = dp[i-1] + dp[i-2]

　　class Solution:

　　def climbStairs(self, n: int) -> int:

　　dp = [0, 1, 2]

　　i = 3

　　while i <= n:

　　dp.append(dp[i-1] + dp[i-2])

　　i = i + 1

　　return dp[n]

　　Medium難度

　　Easy難度的都是一維DP，到了Medium難度一般都是二維DP了或者有條件的一維DP。好的講解動(dòng)態(tài)規(guī)劃的文章都只介紹了一維的DP，導(dǎo)致看完之后覺(jué)得很簡(jiǎn)單，到實(shí)際做起題來(lái)發(fā)現(xiàn)無(wú)從下手。二維DP的矩陣，當(dāng)前dp[i,j]一般與三個(gè)值有關(guān)，即 dp[i-1][j], dp[i][j-1]和dp[i-1][j-1]。

　　62. 不同路徑

　　分析：

　　1. 狀態(tài)轉(zhuǎn)移方程：到達(dá)終點(diǎn)可以分成兩部分，第一部分從終點(diǎn)上方到達(dá)終點(diǎn)如紅線(xiàn)所示，或者從終點(diǎn)左邊到達(dá)終點(diǎn)如藍(lán)線(xiàn)所示。那么到達(dá)終點(diǎn)的路徑總數(shù)就等于紅線(xiàn)總數(shù)加上藍(lán)線(xiàn)總數(shù)(因?yàn)椴豢梢孕敝?，因此狀態(tài)轉(zhuǎn)移方程為 dp[i][j] = dp[i-1][j] + dp[i][j-1]

　　2. 初始條件： 終點(diǎn)和起點(diǎn)重合時(shí)候只有一條路徑，因此dp[1][1] = 1

　　class Solution:

　　def uniquePaths(self, m: int, n: int):

　　dp = [([0] * (n+1)) for i in range(m+1)] # create 2d array

　　for i in range(1, m+1):

　　for j in range(1, n+1):

　　if i == 1 and j == 1:

　　dp[i][j] = 1

　　else:

　　dp[i][j] = dp[i-1][j] + dp[i][j-1]

　　return dp[m][n]

　　P.S.：二維DP一般DP矩陣會(huì)比原始數(shù)據(jù)大一圈，一是為了符合真實(shí)環(huán)境，二是DP很多初始時(shí)刻值都為0

　　63. 不同路徑 II

　　分析：

　　1. 狀態(tài)轉(zhuǎn)移方程：這道題和上面一道題類(lèi)似，只不過(guò)加了一些限定條件。如圖所示，如果終點(diǎn)上方存在障礙物，那么從終點(diǎn)上面的路徑將全部失效，如果左邊上方存在障礙物，那么從終點(diǎn)左邊的路徑將全部失效。而有沒(méi)有障礙物已經(jīng)給出，因此狀態(tài)轉(zhuǎn)移方程為： dp[i][j] = dp[i-1][j] * (1 - obstacleGrid[i-2][j-1]) + dp[i][j-1] * (1 - obstacleGrid[i-1][j-2])

　　2. 初始條件： 終點(diǎn)和起點(diǎn)重合時(shí)候只有一條路徑，因此dp[1][1] = 1

　　3. 特殊情況：當(dāng)障礙物在終點(diǎn)時(shí)，無(wú)論多大，路徑都不存在

　　class Solution:

　　def uniquePathsWithObstacles(self, obstacleGrid):

　　m = len(obstacleGrid)

　　n = len(obstacleGrid[0])

　　if obstacleGrid[m-1][n-1] == 1:

　　return 0

　　dp = [([0] * (n+1)) for i in range(m+1)]

　　for i in range(1, m+1):

　　for j in range(1, n+1):

　　# print(i,j)

　　if i == 1 and j == 1:

　　dp[i][j] = 1 - obstacleGrid[i-1][j-1]

　　else:

　　dp[i][j] = dp[i-1][j] * (1 - obstacleGrid[i-2][j-1]) + dp[i][j-1] * (1 - obstacleGrid[i-1][j-2])

　　return dp[m][n]

　　64. 最小路徑和

　　分析：這題和上面幾題類(lèi)似

　　1. 狀態(tài)轉(zhuǎn)移方程：如圖所示，假設(shè)只有矩陣[[1,3],[1,5]]，那么以5作為終點(diǎn)的話(huà)有兩條路徑，一條從上方過(guò)來(lái)，另一條從左邊過(guò)來(lái)。由于題目要求最小路徑，因此選取紅線(xiàn)和藍(lán)線(xiàn)中的較小者，加上該點(diǎn)的值就是該點(diǎn)作為終點(diǎn)DP的值。因此，狀態(tài)轉(zhuǎn)移方程為： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]

　　2. 邊界條件：當(dāng)只有一行時(shí)，該路徑為這一行的和 dp[i][j] = dp[i][j-1] + grid[i-1][j-1];只有一列時(shí)，該路徑為這一列的和 dp[i][j] = dp[i-1][j] + grid[i-1][j-1]

　　class Solution:

　　def minPathSum(self, grid):

　　m = len(grid)

　　n = len(grid[0])

　　dp = [([0] * (n+1)) for i in range(m+1)]

　　for i in range(1, m+1):

　　for j in range(1, n+1):

　　if i == 1:

　　dp[i][j] = dp[i][j-1] + grid[i-1][j-1]

　　elif j == 1:

　　dp[i][j] = dp[i-1][j] + grid[i-1][j-1]

　　else:

　　dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]

　　return dp[m][n]

　　96. 不同的二叉搜索樹(shù)

　　分析：一維DP，不過(guò)狀態(tài)轉(zhuǎn)移方程有點(diǎn)復(fù)雜

　　1. 狀態(tài)轉(zhuǎn)移方程： 本題是在樹(shù)結(jié)構(gòu)下的DP，首先我們可以知道dp[1] = 1, dp[2] = 2, dp[3] = 5， 看上去沒(méi)有任何聯(lián)系。這道題一開(kāi)始一頭霧水，因?yàn)檎也坏阶咏Y(jié)構(gòu)。在樹(shù)的背景下就要考慮樹(shù)結(jié)構(gòu)的特點(diǎn)。一個(gè)二叉樹(shù)分為左子樹(shù)和右子樹(shù)，而左右子樹(shù)的元素?cái)?shù)為n-1(減去根節(jié)點(diǎn))。那么很容易想到將n-1分解成兩個(gè)數(shù)的和，這兩個(gè)數(shù)分別為左右子樹(shù)元素?cái)?shù)目。左右子樹(shù)元素必定少于n，那么就可以查表找到對(duì)應(yīng)的搜索樹(shù)數(shù)目，分析到這子結(jié)構(gòu)就確定了。下面看狀態(tài)轉(zhuǎn)移方程，以n=2為例，如圖所示

　　當(dāng)n=2時(shí)，有兩種情況，以1為根節(jié)點(diǎn)，那么剩余元素2。此時(shí)左子樹(shù)只有0個(gè)元素，因此二叉搜索樹(shù)總數(shù)為dp[0]，右子樹(shù)有1個(gè)元素，二叉搜索樹(shù)總數(shù)為dp[1];另一種是以2為根節(jié)點(diǎn)，此時(shí)情況與以1為根節(jié)點(diǎn)情況相反。因此可以得出狀態(tài)轉(zhuǎn)移方程為

　　class Solution:

　　def numTrees(self, n: int) -> int:

　　dp = [0] * (n+1)

　　dp[0] = 1

　　dp[1] = 1

　　for i in range(2, n+1):

　　for j in range(i):

　　dp[i] += dp[i-1-j] * dp[j]

　　return dp[-1]

　　120. 三角形最小路徑和

　　分析：自底向上的DP

　　1. 狀態(tài)轉(zhuǎn)移方程：這道題如果都是整數(shù)那么會(huì)簡(jiǎn)單很多，引入了負(fù)數(shù)就需要考慮到所有情況。因此需要計(jì)算所有可能性的值，采用自底向上的方法。從倒數(shù)第二層開(kāi)始，計(jì)算每一層所有可能的最小值。那么，第二層所有可能最小值如圖所示為[7,6,10]

　　由此可得，狀態(tài)轉(zhuǎn)移方程為 dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]。

　　class Solution:

　　def minimumTotal(self, triangle):

　　n = len(triangle)

　　dp = triangle[-1]

　　i = n-2

　　while i >=0:

　　j = 0無(wú)錫人流醫(yī)院 http://www.bhnkyy39.com/

　　while j <= len(triangle[i])-1:

　　dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]

　　j += 1

　　i -= 1

　　return dp[0]

　　304. 二維區(qū)域和檢索 - 矩陣不可變

　　分析：303. 區(qū)域和檢索 - 數(shù)組不可變的基礎(chǔ)之上，擴(kuò)充到二維

　　狀態(tài)轉(zhuǎn)移方程：矩陣可以分解成一行一行來(lái)看，對(duì)于被選中的一行來(lái)說(shuō)，我們假設(shè)row_dp[j]表示這一行截止到j(luò)的所有元素之和。那么選中局限區(qū)域內(nèi)的值為row_dp[col2] - row_dp[col1-1]。如圖所示，紅色框出來(lái)的那一行row_dp = [1,3,3,4,9],被選中區(qū)域的值為row_dp[3] - row_dp[0] = 4 - 1 = 3。因此狀態(tài)轉(zhuǎn)移方程為：row_dp[j] = row_dp[j-1] + matrix[i][j]。對(duì)每一行都這樣處理就可以得到整個(gè)矩陣的dp

　　class NumMatrix:

　　def __init__(self, matrix):

　　m = len(matrix)

　　if m == 0:

　　self.dp = None

　　return

　　n = len(matrix[0])

　　dp = []

　　for i in range(m):

　　row_dp = [matrix[i][0]]

　　for j in range(1, n):

　　row_dp.append(row_dp[j-1] + matrix[i][j])

　　dp.append(row_dp)

　　self.dp = dp

　　def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:

　　result = 0

　　i = row1

　　while i <= row2:

　　if col1 != 0:

　　result += self.dp[i][col2] - self.dp[i][col1-1]

　　else:

　　result += self.dp[i][col2]

　　i += 1

　　return result