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