資料結構與演算法之動態規劃

語言: CN / TW / HK
時間 2023-02-15 07:15:04

theme: nico

開啟掘金成長之旅！這是我參與「掘金日新計劃 · 2 月更文挑戰」的第 12 天，點選檢視活動詳情

作者： 千石
支援：點贊、收藏、評論
歡迎各位在評論區交流

前言

本文內容來自我平時學習的一些積累，如有錯誤，還請指正

在題目實戰部分，我將程式碼實現和程式碼解釋設定在瞭解題思路的下方，方便各位作為參考刷題

一些話

本文內容來自我平時學習的一些積累，如有錯誤，還請指正

在題目實戰部分，我將程式碼實現和程式碼解釋設定在瞭解題思路的下方，方便各位作為參考刷題

題目練習步驟：

  1. 給自己10分鐘，讀題並思考解題思路
  2. 有了思路以後開始寫程式碼，如果在上一步驟中沒有思路則停止思考並且看該題題解
  3. 在看懂題解（暫時沒看懂也沒關係）的思路後，背誦默寫題解，直至能熟練寫出來
  4. 隔一段時間，再次嘗試寫這道題目

前置知識

動態規劃是一種解決最優化問題的演算法。它通過將原問題劃分為若干個子問題，然後從子問題到原問題依次遞推，從而得到最終結果。

動態規劃的主要實現關鍵點如下：

  1. 狀態轉移：該步驟定義了通過當前狀態如何轉移到下一個狀態。

  2. 狀態儲存：該步驟定義瞭如何儲存當前狀態以便在以後的轉移中使用。

  3. 狀態初始化：該步驟定義瞭如何初始化問題的起始狀態。

  4. 邊界處理：該步驟定義了在達到邊界條件時該如何處理狀態。

  5. 狀態重複：該步驟定義瞭如何避免狀態重複計算。

動態規劃是一種非常有效的解決優化問題的演算法，但是它需要對問題有一定的理解和分析。如果不理解動態規劃的基本原理，很難正確地實現該演算法。

題目

題目一：62. 不同路徑

image.png

思路

我們可以用一個二維陣列 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)，因為我們需要儲存每一個點到終點的不同路徑數。

結果展示

image.png

題目二：63. 不同路徑 II

image.png

思路

我們可以用一個二維陣列 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)，因為我們需要儲存每一個點到終點的不同路徑數。

結果展示

image.png

題目三：劍指 Offer II 095. 最長公共子序列

image.png

思路

把大問題分解為若干個子問題，解決每一個子問題，組合成原問題的解。我們可以用一個二維的陣列 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 的長度。

結果展示

image.png

「」
「」