Easy難度
Easy難度的都是一維DP，前面幾道都是我們在學習dp的時候經常會遇到的例題。我認為dp的關鍵在于最優子結構的選擇，最優子結構選擇好了對應的狀态轉移就可以很容易的求解。建議把一些常用的最優子結構背下來(就跟當初背快排一樣)，遇到類似的題目直接套用或者改變就好了。我的dp解題思路為 确定使用動态規劃->确定最優子結構->确定狀态轉移方程->确定邊界條件。動态規劃并不是一種具體的解題方法，沒有萬能的公式可以套，而是一種解題的思維方法。
53. 最大子序和
分析：對于包含負數的求和容易陷入局部最優解而忽略全局最優解。
最優子結構：假設dp[i]表示以j結尾的最大子序列，也可以假設dp[i,j]為以i為起點j為終點的最大子序和，這種子結構明顯比第一種複雜。
狀态轉移方程：最優子結構确定後可以确定狀态轉移方程了，假設i-1時的sum為正數，那麼以i結尾的子序和為dp[i-1] + nums[i];如果目前sum為負數，那麼不論nums[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還有一種簡單的解法就是采用數學歸納法，首先計算前幾項，然後歸納出一個一般通項。這裡不需要嚴格證明，一般歸納的結果都是正确的，這裡用這種方法作為解法。
最優子結構：對于一級台階i，最後一步可能有兩種情況，即從i-1上來，或者從i-2上來。
狀态轉移方程：采用數學歸納法：假設台階數為n，方法數為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)
容易發現 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。好的講解動态規劃的文章都隻介紹了一維的DP，導緻看完之後覺得很簡單，到實際做起題來發現無從下手。二維DP的矩陣，目前dp[i,j]一般與三個值有關，即 dp[i-1][j], dp[i][j-1]和dp[i-1][j-1]。
62. 不同路徑
分析：
1. 狀态轉移方程：到達終點可以分成兩部分，第一部分從終點上方到達終點如紅線所示，或者從終點左邊到達終點如藍線所示。那麼到達終點的路徑總數就等于紅線總數加上藍線總數(因為不可以斜着走)，是以狀态轉移方程為 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矩陣會比原始資料大一圈，一是為了符合真實環境，二是DP很多初始時刻值都為0
63. 不同路徑 II
分析：
1. 狀态轉移方程：這道題和上面一道題類似，隻不過加了一些限定條件。如圖所示，如果終點上方存在障礙物，那麼從終點上面的路徑将全部失效，如果左邊上方存在障礙物，那麼從終點左邊的路徑将全部失效。而有沒有障礙物已經給出，是以狀态轉移方程為： 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. 狀态轉移方程：如圖所示，假設隻有矩陣[[1,3],[1,5]]，那麼以5作為終點的話有兩條路徑，一條從上方過來，另一條從左邊過來。由于題目要求最小路徑，是以選取紅線和藍線中的較小者，加上該點的值就是該點作為終點DP的值。是以，狀态轉移方程為： 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，不過狀态轉移方程有點複雜
1. 狀态轉移方程： 本題是在樹結構下的DP，首先我們可以知道dp[1] = 1, dp[2] = 2, dp[3] = 5， 看上去沒有任何聯系。這道題一開始一頭霧水，因為找不到子結構。在樹的背景下就要考慮樹結構的特點。一個二叉樹分為左子樹和右子樹，而左右子樹的元素數為n-1(減去根節點)。那麼很容易想到将n-1分解成兩個數的和，這兩個數分别為左右子樹元素數目。左右子樹元素必定少于n，那麼就可以查表找到對應的搜尋樹數目，分析到這子結構就确定了。下面看狀态轉移方程，以n=2為例，如圖所示
當n=2時，有兩種情況，以1為根節點，那麼剩餘元素2。此時左子樹隻有0個元素，是以二叉搜尋樹總數為dp[0]，右子樹有1個元素，二叉搜尋樹總數為dp[1];另一種是以2為根節點，此時情況與以1為根節點情況相反。是以可以得出狀态轉移方程為
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. 狀态轉移方程：這道題如果都是整數那麼會簡單很多，引入了負數就需要考慮到所有情況。是以需要計算所有可能性的值，采用自底向上的方法。從倒數第二層開始，計算每一層所有可能的最小值。那麼，第二層所有可能最小值如圖所示為[7,6,10]
由此可得，狀态轉移方程為 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無錫人流醫院 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. 二維區域和檢索 - 矩陣不可變
分析：303. 區域和檢索 - 數組不可變的基礎之上，擴充到二維
狀态轉移方程：矩陣可以分解成一行一行來看，對于被選中的一行來說，我們假設row_dp[j]表示這一行截止到j的所有元素之和。那麼選中局限區域内的值為row_dp[col2] - row_dp[col1-1]。如圖所示，紅色框出來的那一行row_dp = [1,3,3,4,9],被選中區域的值為row_dp[3] - row_dp[0] = 4 - 1 = 3。是以狀态轉移方程為：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