Easy難度

十載的瀾滄網(wǎng)站建設經(jīng)驗，針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。成都全網(wǎng)營銷的優(yōu)勢是能夠根據(jù)用戶設備顯示端的尺寸不同，自動調整瀾滄建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設計，從而大程度地提升瀏覽體驗。創(chuàng)新互聯(lián)從事“瀾滄網(wǎng)站設計”,“瀾滄網(wǎng)站推廣”以來，每個客戶項目都認真落實執(zhí)行。

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

53. 最大子序和

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

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

狀態(tài)轉移方程：最優(yōu)子結構確定后可以確定狀態(tài)轉移方程了，假設i-1時的sum為正數(shù)，那么以i結尾的子序和為dp[i-1] + nums[i];如果當前sum為負數(shù)，那么不論nums[i]是正是負，加上一個負數(shù)之后都會減小，直接不加就完事了。因此狀態(tài)轉移方程為：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還有一種簡單的解法就是采用數(shù)學歸納法，首先計算前幾項，然后歸納出一個一般通項。這里不需要嚴格證明，一般歸納的結果都是正確的，這里用這種方法作為解法。

最優(yōu)子結構：對于一級臺階i，最后一步可能有兩種情況，即從i-1上來，或者從i-2上來。

狀態(tài)轉移方程：采用數(shù)學歸納法：假設臺階數(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。好的講解動態(tài)規(guī)劃的文章都只介紹了一維的DP，導致看完之后覺得很簡單，到實際做起題來發(fā)現(xiàn)無從下手。二維DP的矩陣，當前dp[i,j]一般與三個值有關，即 dp[i-1][j], dp[i][j-1]和dp[i-1][j-1]。

62. 不同路徑

分析：

1. 狀態(tài)轉移方程：到達終點可以分成兩部分，第一部分從終點上方到達終點如紅線所示，或者從終點左邊到達終點如藍線所示。那么到達終點的路徑總數(shù)就等于紅線總數(shù)加上藍線總數(shù)(因為不可以斜著走)，因此狀態(tài)轉移方程為 dp[i][j] = dp[i-1][j] + dp[i][j-1]

2. 初始條件： 終點和起點重合時候只有一條路徑，因此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矩陣會比原始數(shù)據(jù)大一圈，一是為了符合真實環(huán)境，二是DP很多初始時刻值都為0

63. 不同路徑 II

分析：

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

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

3. 特殊情況：當障礙物在終點時，無論多大，路徑都不存在

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. 最小路徑和

分析：這題和上面幾題類似

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

2. 邊界條件：當只有一行時，該路徑為這一行的和 dp[i][j] = dp[i][j-1] + grid[i-1][j-1];只有一列時，該路徑為這一列的和 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. 不同的二叉搜索樹

分析：一維DP，不過狀態(tài)轉移方程有點復雜

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

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

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)轉移方程：這道題如果都是整數(shù)那么會簡單很多，引入了負數(shù)就需要考慮到所有情況。因此需要計算所有可能性的值，采用自底向上的方法。從倒數(shù)第二層開始，計算每一層所有可能的最小值。那么，第二層所有可能最小值如圖所示為[7,6,10]

由此可得，狀態(tài)轉移方程為 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無錫人流醫(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ù)組不可變的基礎之上，擴充到二維

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