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