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