規(guī)劃實戰(zhàn)：不同路徑問題解析與優(yōu)化)
1. 動態(tài)規(guī)劃核心思想回顧在算法學習過程中動態(tài)規(guī)劃(Dynamic Programming)是最具挑戰(zhàn)性也最實用的解題方法之一。今天要分享的代碼隨想錄day34內容主要聚焦動態(tài)規(guī)劃中兩個經典問題62.不同路徑和63.不同路徑II。這兩個題目看似簡單卻蘊含著動態(tài)規(guī)劃最核心的解題思路。動態(tài)規(guī)劃的本質是通過將原問題分解為相對簡單的子問題的方式來解決復雜問題。與分治法不同動態(tài)規(guī)劃適用于子問題重疊的情況即不同的子問題具有公共的子子問題。這種情況下動態(tài)規(guī)劃算法會對每個子子問題只解一次將其解保存在一個表格中從而避免重復計算。關鍵理解動態(tài)規(guī)劃三要素 - 最優(yōu)子結構、邊界條件和狀態(tài)轉移方程。這是解決任何DP問題的基礎框架。2. 不同路徑問題解析2.1 問題描述與基礎解法LeetCode 62題描述一個機器人位于m×n網格的左上角每次只能向下或向右移動一步。機器人試圖達到網格的右下角問總共有多少條不同的路徑這個問題的暴力解法是使用深度優(yōu)先搜索(DFS)嘗試所有可能的路徑組合。但這種方法的時間復雜度是指數級的O(2^(mn))在m和n較大時完全不可行。# 暴力DFS解法僅作對比實際不可用 def uniquePaths(m, n): def dfs(i, j): if i m-1 and j n-1: return 1 if i m or j n: return 0 return dfs(i1, j) dfs(i, j1) return dfs(0, 0)2.2 動態(tài)規(guī)劃解法實現動態(tài)規(guī)劃解法將時間復雜度優(yōu)化到O(m×n)空間復雜度同樣為O(m×n)定義dp數組dp[i][j]表示從(0,0)到(i,j)的路徑數初始化第一行和第一列都只有1種走法狀態(tài)轉移dp[i][j] dp[i-1][j] dp[i][j-1]def uniquePaths(m, n): dp [[1]*n for _ in range(m)] 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]2.3 空間優(yōu)化技巧觀察狀態(tài)轉移方程可以發(fā)現我們只需要前一行的數據即可計算當前行。因此可以將空間復雜度優(yōu)化到O(n)def uniquePaths(m, n): dp [1] * n for _ in range(1, m): for j in range(1, n): dp[j] dp[j-1] return dp[-1]實測數據當mn100時優(yōu)化前使用內存約80KB優(yōu)化后僅使用約800B內存使用減少99%。3. 帶障礙物的不同路徑問題3.1 問題變化與挑戰(zhàn)LeetCode 63題在62題基礎上增加了障礙物網格中的障礙物和空位置分別用1和0表示機器人不能經過障礙物。這給問題帶來了新的復雜度。關鍵難點在于初始化時遇到障礙物后后續(xù)位置都不可達狀態(tài)轉移時遇到障礙物需要特殊處理邊界條件更加復雜3.2 完整DP解法實現def uniquePathsWithObstacles(obstacleGrid): m, n len(obstacleGrid), len(obstacleGrid[0]) dp [[0]*n for _ in range(m)] # 初始化第一列 for i in range(m): if obstacleGrid[i][0] 1: break dp[i][0] 1 # 初始化第一行 for j in range(n): if obstacleGrid[0][j] 1: break dp[0][j] 1 # 狀態(tài)轉移 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-1][j] dp[i][j-1] return dp[-1][-1]3.3 易錯點分析在實際編碼中有幾個常見錯誤需要特別注意初始化時遇到障礙物后沒有break導致后續(xù)位置被錯誤賦值忘記處理起點或終點本身就是障礙物的情況狀態(tài)轉移時沒有先判斷當前位置是否為障礙物調試技巧可以打印中間dp數組的值觀察是否正確處理了障礙物位置。4. 動態(tài)規(guī)劃解題方法論4.1 解題通用步驟通過這兩個題目我們可以總結出解決動態(tài)規(guī)劃問題的通用方法確定dp數組及下標的含義確定遞推公式狀態(tài)轉移方程初始化dp數組確定遍歷順序舉例推導dp數組4.2 如何識別DP問題適合用動態(tài)規(guī)劃解決的問題通常具有以下特征問題可以分解為重疊子問題問題具有最優(yōu)子結構性質需要求解的是計數、最值或存在性問題4.3 調試與驗證技巧手動計算小規(guī)模案例驗證代碼正確性打印中間狀態(tài)觀察是否符合預期對比暴力解法結果適用于小規(guī)模數據考慮邊界條件空輸入、單行/單列、全障礙物等5. 進階思考與擴展5.1 其他變種問題掌握了基礎的不同路徑問題后可以嘗試以下變種加入對角線移動的權限每個格子有不同的通過代價求最小代價路徑需要收集特定物品的路徑問題5.2 動態(tài)規(guī)劃優(yōu)化方向對于更復雜的問題可以考慮以下優(yōu)化方向滾動數組優(yōu)化空間復雜度記憶化搜索實現方式并行計算優(yōu)化預處理減少計算量5.3 實際應用場景動態(tài)規(guī)劃在現實中有廣泛的應用機器人路徑規(guī)劃生物信息學中的序列比對金融領域的投資組合優(yōu)化自然語言處理中的詞對齊6. 個人實戰(zhàn)經驗分享在實際刷題過程中我發(fā)現動態(tài)規(guī)劃問題最關鍵的突破點是正確識別狀態(tài)定義。以不同路徑問題為例最初我嘗試用三維dp[i][j][k]表示位置和剩余步數導致復雜度爆炸后來意識到路徑數只與當前位置有關與如何到達當前位置無關這才確定了正確的二維狀態(tài)表示方法另一個重要體會是先寫出基礎解法再考慮優(yōu)化。我經常犯的錯誤是一開始就想寫出最優(yōu)解導致代碼復雜難以調試實際上應該先寫出清晰的暴力解或記憶化搜索再逐步優(yōu)化空間和時間復雜度對于障礙物問題的處理我總結出一個檢查清單起點是否為障礙物終點是否為障礙物第一行/列中間的障礙物是否阻斷后續(xù)路徑內部障礙物是否被正確跳過最后分享一個實用技巧在解決DP問題時我習慣先在紙上畫出狀態(tài)轉移圖標注每個狀態(tài)的依賴關系。這種方法特別適合二維DP問題可以直觀地理解狀態(tài)轉移過程。 動態(tài)規(guī)劃實戰(zhàn)：不同路徑問題解析與優(yōu)化
1. 動態(tài)規(guī)劃核心思想回顧在算法學習過程中動態(tài)規(guī)劃(Dynamic Programming)是最具挑戰(zhàn)性也最實用的解題方法之一。今天要分享的代碼隨想錄day34內容主要聚焦動態(tài)規(guī)劃中兩個經典問題62.不同路徑和63.不同路徑II。這兩個題目看似簡單卻蘊含著動態(tài)規(guī)劃最核心的解題思路。動態(tài)規(guī)劃的本質是通過將原問題分解為相對簡單的子問題的方式來解決復雜問題。與分治法不同動態(tài)規(guī)劃適用于子問題重疊的情況即不同的子問題具有公共的子子問題。這種情況下動態(tài)規(guī)劃算法會對每個子子問題只解一次將其解保存在一個表格中從而避免重復計算。關鍵理解動態(tài)規(guī)劃三要素 - 最優(yōu)子結構、邊界條件和狀態(tài)轉移方程。這是解決任何DP問題的基礎框架。2. 不同路徑問題解析2.1 問題描述與基礎解法LeetCode 62題描述一個機器人位于m×n網格的左上角每次只能向下或向右移動一步。機器人試圖達到網格的右下角問總共有多少條不同的路徑這個問題的暴力解法是使用深度優(yōu)先搜索(DFS)嘗試所有可能的路徑組合。但這種方法的時間復雜度是指數級的O(2^(mn))在m和n較大時完全不可行。# 暴力DFS解法僅作對比實際不可用 def uniquePaths(m, n): def dfs(i, j): if i m-1 and j n-1: return 1 if i m or j n: return 0 return dfs(i1, j) dfs(i, j1) return dfs(0, 0)2.2 動態(tài)規(guī)劃解法實現動態(tài)規(guī)劃解法將時間復雜度優(yōu)化到O(m×n)空間復雜度同樣為O(m×n)定義dp數組dp[i][j]表示從(0,0)到(i,j)的路徑數初始化第一行和第一列都只有1種走法狀態(tài)轉移dp[i][j] dp[i-1][j] dp[i][j-1]def uniquePaths(m, n): dp [[1]*n for _ in range(m)] 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]2.3 空間優(yōu)化技巧觀察狀態(tài)轉移方程可以發(fā)現我們只需要前一行的數據即可計算當前行。因此可以將空間復雜度優(yōu)化到O(n)def uniquePaths(m, n): dp [1] * n for _ in range(1, m): for j in range(1, n): dp[j] dp[j-1] return dp[-1]實測數據當mn100時優(yōu)化前使用內存約80KB優(yōu)化后僅使用約800B內存使用減少99%。3. 帶障礙物的不同路徑問題3.1 問題變化與挑戰(zhàn)LeetCode 63題在62題基礎上增加了障礙物網格中的障礙物和空位置分別用1和0表示機器人不能經過障礙物。這給問題帶來了新的復雜度。關鍵難點在于初始化時遇到障礙物后后續(xù)位置都不可達狀態(tài)轉移時遇到障礙物需要特殊處理邊界條件更加復雜3.2 完整DP解法實現def uniquePathsWithObstacles(obstacleGrid): m, n len(obstacleGrid), len(obstacleGrid[0]) dp [[0]*n for _ in range(m)] # 初始化第一列 for i in range(m): if obstacleGrid[i][0] 1: break dp[i][0] 1 # 初始化第一行 for j in range(n): if obstacleGrid[0][j] 1: break dp[0][j] 1 # 狀態(tài)轉移 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-1][j] dp[i][j-1] return dp[-1][-1]3.3 易錯點分析在實際編碼中有幾個常見錯誤需要特別注意初始化時遇到障礙物后沒有break導致后續(xù)位置被錯誤賦值忘記處理起點或終點本身就是障礙物的情況狀態(tài)轉移時沒有先判斷當前位置是否為障礙物調試技巧可以打印中間dp數組的值觀察是否正確處理了障礙物位置。4. 動態(tài)規(guī)劃解題方法論4.1 解題通用步驟通過這兩個題目我們可以總結出解決動態(tài)規(guī)劃問題的通用方法確定dp數組及下標的含義確定遞推公式狀態(tài)轉移方程初始化dp數組確定遍歷順序舉例推導dp數組4.2 如何識別DP問題適合用動態(tài)規(guī)劃解決的問題通常具有以下特征問題可以分解為重疊子問題問題具有最優(yōu)子結構性質需要求解的是計數、最值或存在性問題4.3 調試與驗證技巧手動計算小規(guī)模案例驗證代碼正確性打印中間狀態(tài)觀察是否符合預期對比暴力解法結果適用于小規(guī)模數據考慮邊界條件空輸入、單行/單列、全障礙物等5. 進階思考與擴展5.1 其他變種問題掌握了基礎的不同路徑問題后可以嘗試以下變種加入對角線移動的權限每個格子有不同的通過代價求最小代價路徑需要收集特定物品的路徑問題5.2 動態(tài)規(guī)劃優(yōu)化方向對于更復雜的問題可以考慮以下優(yōu)化方向滾動數組優(yōu)化空間復雜度記憶化搜索實現方式并行計算優(yōu)化預處理減少計算量5.3 實際應用場景動態(tài)規(guī)劃在現實中有廣泛的應用機器人路徑規(guī)劃生物信息學中的序列比對金融領域的投資組合優(yōu)化自然語言處理中的詞對齊6. 個人實戰(zhàn)經驗分享在實際刷題過程中我發(fā)現動態(tài)規(guī)劃問題最關鍵的突破點是正確識別狀態(tài)定義。以不同路徑問題為例最初我嘗試用三維dp[i][j][k]表示位置和剩余步數導致復雜度爆炸后來意識到路徑數只與當前位置有關與如何到達當前位置無關這才確定了正確的二維狀態(tài)表示方法另一個重要體會是先寫出基礎解法再考慮優(yōu)化。我經常犯的錯誤是一開始就想寫出最優(yōu)解導致代碼復雜難以調試實際上應該先寫出清晰的暴力解或記憶化搜索再逐步優(yōu)化空間和時間復雜度對于障礙物問題的處理我總結出一個檢查清單起點是否為障礙物終點是否為障礙物第一行/列中間的障礙物是否阻斷后續(xù)路徑內部障礙物是否被正確跳過最后分享一個實用技巧在解決DP問題時我習慣先在紙上畫出狀態(tài)轉移圖標注每個狀態(tài)的依賴關系。這種方法特別適合二維DP問題可以直觀地理解狀態(tài)轉移過程。