資料結構與演算法之動態規劃
theme: nico
開啟掘金成長之旅!這是我參與「掘金日新計劃 · 2 月更文挑戰」的第 12 天,點選檢視活動詳情
作者: 千石
支援:點贊、收藏、評論
歡迎各位在評論區交流
前言
本文內容來自我平時學習的一些積累,如有錯誤,還請指正
在題目實戰部分,我將程式碼實現和程式碼解釋設定在瞭解題思路的下方,方便各位作為參考刷題
一些話
本文內容來自我平時學習的一些積累,如有錯誤,還請指正
在題目實戰部分,我將程式碼實現和程式碼解釋設定在瞭解題思路的下方,方便各位作為參考刷題
題目練習步驟:
- 給自己10分鐘,讀題並思考解題思路
- 有了思路以後開始寫程式碼,如果在上一步驟中沒有思路則停止思考並且看該題題解
- 在看懂題解(暫時沒看懂也沒關係)的思路後,背誦默寫題解,直至能熟練寫出來
- 隔一段時間,再次嘗試寫這道題目
前置知識
動態規劃是一種解決最優化問題的演算法。它通過將原問題劃分為若干個子問題,然後從子問題到原問題依次遞推,從而得到最終結果。
動態規劃的主要實現關鍵點如下:
-
狀態轉移:該步驟定義了通過當前狀態如何轉移到下一個狀態。
-
狀態儲存:該步驟定義瞭如何儲存當前狀態以便在以後的轉移中使用。
-
狀態初始化:該步驟定義瞭如何初始化問題的起始狀態。
-
邊界處理:該步驟定義了在達到邊界條件時該如何處理狀態。
-
狀態重複:該步驟定義瞭如何避免狀態重複計算。
動態規劃是一種非常有效的解決優化問題的演算法,但是它需要對問題有一定的理解和分析。如果不理解動態規劃的基本原理,很難正確地實現該演算法。
題目
題目一:62. 不同路徑
思路
我們可以用一個二維陣列 dp 來儲存每一個點到終點的不同路徑數。從終點的點開始,將該點設為1,然後分別更新該點上方和左邊的點的路徑數,即 dp[i][j] = dp[i][j-1] + dp[i-1][j]。最終,我們可以返回 dp[m-1][n-1],它表示到網格的右下角的不同路徑數。
程式碼實現
python
def uniquePaths(m, n):
dp = [[0] * n for _ in range(m)]
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i][j-1] + dp[i-1][j]
return dp[m-1][n-1]
複雜度分析
我們只需要更新網格中的所有點一次,因此時間複雜度為 O(mn)。空間複雜度為 O(mn),因為我們需要儲存每一個點到終點的不同路徑數。
結果展示
題目二:63. 不同路徑 II
思路
我們可以用一個二維陣列 dp 來儲存每一個點到終點的不同路徑數。如果一個點是障礙物,那麼我們就將它的路徑數設為0,否則它的路徑數是從該點上方和左邊的點的路徑數之和,即 dp[i][j] = dp[i][j-1] + dp[i-1][j]。最終,我們可以返回 dp[m-1][n-1],它表示到網格的右下角的不同路徑數。
程式碼展示
python
def uniquePathsWithObstacles(obstacleGrid):
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1 - obstacleGrid[0][0]
for i in range(1, m):
dp[i][0] = dp[i-1][0] * (1 - obstacleGrid[i][0])
for j in range(1, n):
dp[0][j] = dp[0][j-1] * (1 - obstacleGrid[0][j])
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i][j-1] + dp[i-1][j]
return dp[m-1][n-1]
複雜度分析
我們只需要更新網格中的所有點一次,因此時間複雜度為 O(mn)。空間複雜度為 O(mn),因為我們需要儲存每一個點到終點的不同路徑數。
結果展示
題目三:劍指 Offer II 095. 最長公共子序列
思路
把大問題分解為若干個子問題,解決每一個子問題,組合成原問題的解。我們可以用一個二維的陣列 dp[i][j] 表示 text1 的前 i 個字元與 text2 的前 j 個字元的最長公共子序列的長度。
狀態轉移方程如下:
- 如果 text1[i] == text2[j],那麼 dp[i][j] = dp[i-1][j-1] + 1
- 如果 text1[i] != text2[j],那麼 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
程式碼展示
python
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
複雜度分析
演算法的時間複雜度為 O(m * n),其中 m 和 n 分別為 text1 和 text2 的長度。