動態規劃問題

力扣121：買賣股票（一次交易）

力扣122：買賣股票（多次交易）

力扣134：加油站

力扣309：買賣股票（包含冷凍時間）

力扣322：零錢兌換

力扣518：零錢兌換

力扣53：最大子緒和

力扣674：未經排序數組最長連續遞增序列

把數字翻譯成字符串

剪繩子

接雨水

禮物的最大價值

動態規劃解題步驟

核心思想是遞推，難點在于想清楚 狀態 dp[i] 代表什么，然后構造狀態轉移矩陣，利用初始條件遞推出最終結果

將原問題拆分成子問題

確認狀態

確認邊界狀態（初始條件）

狀態轉移方程

矩陣類型

minimum-path-sum

給定一個包含非負整數的 ?m?x?n? 網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。

思路：動態規劃

state: f(x, y) 從起點走到 (x, y) 的最短路徑

function: f(x, y) = min(f(x - 1, y), f(x, y - 1)) + A(x, y)

intialize: f(0, 0) = A(0, 0)、f(i, 0) = sum(0,0 -> i,0)、 f(0, i) = sum(0,0 -> 0,i)

answer: f(n - 1, m - 1)

class Solution(object):def minPathSum(self, grid):""":type grid: List[List[int]]:rtype: int"""m = len(grid)n = len(grid[0])dp = [[0]*n for _ in range(m)]dp[0][0] = grid[0][0]for i in range(1,m):dp[i][0] = grid[i][0]+dp[i-1][0]for i in range(1,n):dp[0][i] = grid[0][i]+dp[0][i-1]for i in range(1,m):for j in range(1,n):dp[i][j] = min(grid[i][j]+dp[i-1][j],grid[i][j]+dp[i][j-1])return dp[-1][-1]

unique-paths

一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）。 機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。 問總共有多少條不同的路徑？

我們令 dp[i][j] 是到達 i, j 最多路徑

動態方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

注意，對于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在邊界，所以只能為 1

時間復雜度：O(m?n)

空間復雜度：O(m?n)

優化：因為我們每次只需要 dp[i-1][j],dp[i][j-1]

class Solution(object):def uniquePaths(self, m, n):dp = [[0 for _ in range(n)] for _ in range(m)]# 第一行都賦予 1for j in range(n):dp[0][j] = 1# 第一列都賦予 1 for i in range(m):dp[i][0] = 1# 兩個for循環推導，對于(i,j)來說，只能由上方或者左方轉移過來 for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[-1][-1]

unique-paths-ii

一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）。 機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。 問總共有多少條不同的路徑？ 現在考慮網格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？

class Solution(object):def uniquePathsWithObstacles(self, obstacleGrid):n = len(obstacleGrid)m = len(obstacleGrid[0])dp = [[0] * m for _ in range(n)]#(0,0)這個格子可能有障礙物dp[0][0] = 0 if obstacleGrid[0][0] else 1#處理第一列for i in range(1, n):if obstacleGrid[i][0] == 1 or dp[i - 1][0] == 0:dp[i][0] = 0else:dp[i][0] = 1#處理第一行 for j in range(1, m):if obstacleGrid[0][j] == 1 or dp[0][j - 1] == 0:dp[0][j] = 0else:dp[0][j] = 1for i in range(1, n):for j in range(1, m):#如果當前格子是障礙物if obstacleGrid[i][j] == 1:dp[i][j] = 0#路徑總數來自于上方(dp[i-1][j])和左方(dp[i][j-1]) else:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[-1][-1]

序列類型

climbing-stairs

假設你正在爬樓梯。需要 n?階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

class Solution(object):def climbStairs(self, n):dp = [0] * (n + 1)dp[0] = dp[1] = 1for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[-1]

312. 戳氣球

有 n 個氣球，編號為0 到 n - 1，每個氣球上都標有一個數字，這些數字存在數組 nums 中。

現在要求你戳破所有的氣球。戳破第 i 個氣球，你可以獲得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬幣。 這里的 i - 1 和 i + 1 代表和 i 相鄰的兩個氣球的序號。如果 i - 1或 i + 1 超出了數組的邊界，那么就當它是一個數字為 1 的氣球。

求所能獲得硬幣的最大數量。

思路：

dp[i][j]代表i和j之間的球能獲得最大硬幣數，k代表最后一個戳破的氣球則有dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j]。那么dp[i][j]就等于遍歷i和j之間的k，找到最大的那個。

遍歷時，根據i和j之間的區間長度遍歷，因為更長的區間來自更短的區間。這樣通過動態規劃可以得到所有的區間長度。

假設這個區間是個開區間，最左邊索引 i，最右邊索引 j
我這里說 “開區間” 的意思是，我們只能戳爆 i 和 j 之間的氣球，i 和 j 不要戳
?
DP思路是這樣的，就先別管前面是怎么戳的，你只要管這個區間最后一個被戳破的是哪個氣球
這最后一個被戳爆的氣球就是 k
?
k是這個區間 ??最后一個 ??被戳爆的氣球！！！！！

假設最后一個被戳爆的氣球是粉色的，k 就是粉色氣球的索引
?
然后由于 k 是最后一個被戳爆的，所以它被戳爆之前的場景是什么樣子？

因為是最后一個被戳爆的，所以它周邊沒有球了！沒有球了！只有這個開區間首尾的 i 和 j 了！ 這就是為什么DP的狀態轉移方程是只和 i 和 j 位置的數字有關 假設 dp[i][j] 表示開區間 (i,j) 內你能拿到的最多金幣 那么這個情況下 你在 (i,j) 開區間得到的金幣可以由 dp[i][k] 和 dp[k][j] 進行轉移 如果你此刻選擇戳爆氣球 k，那么你得到的金幣數量就是：

那你可能又想問了，戳爆粉色氣球我能獲得 val[i]*val[k]*val[j] 這么多金幣我能理解(因為戳爆 k 的時候只剩下這三個氣球了)， 但為什么前后只要加上 dp[i][k] 和 dp[k][j] 的值就行了呀？ ? 因為 k 是最后一個被戳爆的，所以 (i,j) 區間中 k 兩邊的東西必然是先各自被戳爆了的， 左右兩邊互不干擾，大家可以細品一下 這就是為什么我們 DP 時要看 “最后一個被戳爆的” 氣球，這就是為了讓左右兩邊互不干擾，這大概就是一種分治的思想.

然后呢，你就從 (i,j) 開區間只有三個數字的時候開始計算，儲存每個小區間可以得到金幣的最大值
然后慢慢擴展到更大的區間，利用小區間里已經算好的數字來算更大的區間

class Solution:def maxCoins(self, nums):# nums首尾添加1，方便處理邊界情況nums.insert(0, 1)nums.insert(len(nums), 1)dp = [[0] * (len(nums)) for _ in range(len(nums))]def range_best(i, j):m = 0# k是(i,j)區間內最后一個被戳的氣球for k in range(i + 1, j): # k取值在(i,j)開區間中# 以下都是開區間(i,k), (k,j)left = dp[i][k]right = dp[k][j]tmp = left + nums[i] * nums[k] * nums[j] + rightif tmp > m:m = tmpdp[i][j] = m# 對每一個區間長度進行循環for delta in range(2, len(nums)): # 區間長度 #長度從3開始，n從2開始# 開區間長度會從3一直到len(nums)# 因為這里取的是range，所以最后一個數字是len(nums)-1# 對于每一個區間長度，循環區間開頭的ifor start in range(0, len(nums) - delta): # i+n = len(nums)-1# 計算這個區間的最多金幣range_best(start, start + delta)return dp[0][len(nums) - 1]

121. 買賣股票的最佳時機

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。

如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設計一個算法來計算你所能獲取的最大利潤。

思路:

考慮僅遍歷一遍, 要找到最大利潤, 等價于找到兩個索引a和b, 其中b>a, 且 利潤=prices[b] - prices[a] 最大.

我們來假設自己來購買股票。隨著時間的推移，每天我們都可以選擇出售股票與否。那么，假設在第 i 天，如果我們要在今天賣股票，那么我們能賺多少錢呢？

顯然，如果我們真的在買賣股票，我們肯定會想：如果我是在歷史最低點買的股票就好了！太好了，在題目中，我們只要用一個變量記錄一個歷史最低價格 minprice，我們就可以假設自己的股票是在那天買的。那么我們在第 i 天賣出股票能得到的利潤就是 prices[i] - minprice。

因此，我們只需要遍歷價格數組一遍，記錄歷史最低點，然后在每一天考慮這么一個問題：如果我是在歷史最低點買進的，那么我今天賣出能賺多少錢？當考慮完所有天數之時，我們就得到了最好的答案

以上遍歷包含了所有的情況, 則最大利潤即為其中最大的值.

class Solution:def maxProfit(self, prices: List[int]) -> int:inf = int(1e9)minprice = infmaxprofit = 0for price in prices:maxprofit = max(price - minprice, maxprofit)minprice = min(price, minprice)return maxprofit

238. 除自身以外數組的乘積

長度為 n 的整數數組 nums，其中 n > 1，返回輸出數組 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積。要求不使用除法。

示例：

輸入: [1,2,3,4] 輸出: [24,12,8,6]

思路：

從左往右遍歷一輪，得到每個索引位置左邊所有元素乘積。然后再從右往左，乘以每個索引位置右邊的乘積。

class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:length = len(nums)# L 和 R 分別表示左右兩側的乘積列表L, R, answer = [0]*length, [0]*length, [0]*length# L[i] 為索引 i 左側所有元素的乘積# 對于索引為 '0' 的元素，因為左側沒有元素，所以 L[0] = 1L[0] = 1for i in range(1, length):L[i] = nums[i - 1] * L[i - 1]# R[i] 為索引 i 右側所有元素的乘積# 對于索引為 'length-1' 的元素，因為右側沒有元素，所以 R[length-1] = 1R[length - 1] = 1for i in reversed(range(length - 1)):R[i] = nums[i + 1] * R[i + 1]# 對于索引 i，除 nums[i] 之外其余各元素的乘積就是左側所有元素的乘積乘以右側所有元素的乘積for i in range(length):answer[i] = L[i] * R[i]return answer

?

Two Sequences DP

72. 編輯距離

給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少操作數 。

思路：

dp[i][j] 代表 word1 到 i 位置轉換成 word2 到 j 位置需要最少步數

動態規劃：建立二維數組dp, dp[i][j]代表從word1前i個字符子串到word2前j個字符子串的編輯距離，則：

如果word1[i] == word2[j], dp[i][j] = dp[i-1][j-1]

如果不等，則dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1, 分別對應替換一個字符操作、刪除一個字符、增加一個字符。

開頭增加一行和一列空字符，作為初始化狀態。

那么dp[i][0] 和 dp[0][j] 表示什么呢？

dp[i][0]：? 以下標i-1為結尾的字符串word1，和空字符串word2，最近編輯距離為dp[i][0]。

那么dp[i][0]就應該是i，對word1里的元素全部做刪除操作，

即：dp[i][0] = i;? 同理dp[0][j] = j;

第一行，是 word1 為空變成 word2 最少步數，就是插入操作

第一列，是 word2 為空，需要的最少步數，就是刪除操作

class Solution:def minDistance(self, word1, word2):m = len(word1)n = len(word2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(m+1):dp[i][0] = ifor j in range(n+1):dp[0][j] = jfor i in range(1, m + 1):for j in range(1, n + 1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] ) + 1#print(dp) return dp[-1][-1]

???????

練習

Matrix DP (10%)

• triangle
• minimum-path-sum
• unique-paths
• unique-paths-ii

Sequence (40%)

• climbing-stairs
• jump-game
• jump-game-ii
• palindrome-partitioning-ii
• longest-increasing-subsequence
• word-break

Two Sequences DP (40%)

• longest-common-subsequence
• edit-distance

Backpack & Coin Change (10%)

• coin-change
• backpack
• backpack-ii

總結

以上是生活随笔為你收集整理的LeetCode Hot100 ---- 动态规划专题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。