用DP框架來思考 Minimum Path Sum 最小路徑成本總和_Leetcode #64
題目敘述 Minimum Path Sum
給定一個矩陣，每個格子點代表經過的對應成本。
每回合可以往右移動一格或往下移動一格。
請問從起點左上角 走到 終點右下角的最小路徑成本總和是多少?
測試範例
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
最小成本的路徑: 1 -> 3 -> 1 -> 1 -> 1
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
最小成本的路徑: 1 -> 2 -> 3 -> 6
觀察 路徑的走法
題目已經說每回合可以往右移動一格，或 往下移動一格。
起點在左上角，終點在右下角。
也就是說，假如我現在當下在(x, y)，可以從左邊一格走過來，或上方一格走過來。
怎麼走可以成本最小?
示意圖
如果定義DP[x, y] = DP[y][x] = 從起點走到(x, y)的最小成本
那麼
走到(x, y)的最小成本
= DP[x, y] = DP[y][x]
= (x, y)本身的成本 + 前一步的最小成本
= grid[x, y] + min{ 前一步的可能情況 }
= grid[x, y] + min{ 走到左邊一格的最小成本， 走到上方一格的最小成本}
= grid[x, y] + min{ DP[x-1, y], DP[x, y-1] } 比較直覺的表示法
= grid[y][x] + min{ DP[y][x-1], DP[y-1][x] } 傳統的陣列表示法
演算法 DP動態規劃
1.定義DP狀態
承接觀察點的思考，可以定義DP[x, y] = DP[y][x] = 從起點走到(x, y)的最小成本。
最終所求呢?
最後走到右下角的成本 = DP[ w-1, h-1] = DP[h-1][w-1] 就是最終答案
2.推導DP狀態轉移關係式
承接觀察點的思考與示意圖
走到(x, y)的最小成本
= DP[x, y] = DP[y][x]
= (x, y)本身的成本 + 前一步的最小成本
= grid[x, y] + min{ 前一步的可能情況 }
= grid[x, y] + min{ 走到左邊一格的最小成本， 走到上方一格的最小成本}
= grid[x, y] + min{ DP[x-1, y], DP[x, y-1] } 比較直覺的表示法
= grid[y][x] + min{ DP[y][x-1], DP[y-1][x] } 傳統的陣列表示法
3.釐清DP初始條件
最小規模的問題是什麼?
就是當地圖只剩下1x1的矩陣時，這時候起點=終點。
最小路徑成本 = DP[0][0] = grid[0][0]
程式碼 DP動態規劃(Top-down)
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# height and width of board
h, w = len(grid), len(grid[0])
## dictionary
# key: coordination
# value: minial cost from (0,0) to (x, y)
minCostTable = { (0,0) : grid[0][0] }
def dp(x, y):
# look-up table
if (x, y) in minCostTable:
return minCostTable[(x,y)]
# base case: top row
if x > 0 and y == 0:
minCostTable[(x,y)] = grid[y][x] + dp(x-1, y)
# base case: left-most column
elif y > 0 and x == 0:
minCostTable[(x,y)] = grid[y][x] + dp(x, y-1)
# general cases:
else:
minCostTable[(x,y)] = grid[y][x] + min( dp(x, y-1), dp(x-1, y) )
return minCostTable[(x,y)]
# =================================
return dp(w-1, h-1)
複雜度分析
時間複雜度: O(h*w)
總共有h*w格子點，每個格子點計算最小路徑成本總和一次。
空間複雜度: O(h*w)
DP table儲存每個格子點的最小路徑成本總和，總共有O(h*w)的格子點。
程式碼 DP動態規劃(Bottom-up)
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
h, w = len(grid), len(grid[0])
dp_table = grid
# Base case:
# optimization for row_#0
for x in range(1,w):
dp_table[0][x] = grid[0][x] + dp_table[0][x-1]
# optimization for column_#0
for y in range(1,h):
dp_table[y][0] = grid[y][0] + dp_table[y-1][0]
# General case optimization:
for y in range(1,h):
for x in range(1,w):
dp_table[y][x] = grid[y][x] + min( dp_table[y][x-1], dp_table[y-1][x] )
return dp_table[h-1][w-1]
複雜度分析
時間複雜度: O(h*w)
總共有h*w格子點，每個格子點計算最小路徑成本總和一次。
空間複雜度: O(1)
因為計算順序是從左到右，從上到下依序計算不回頭，這邊採用in-place更新，
所以DP table不會耗費額外的空間。
關鍵知識點 從走法反推最小成本路徑的生成模式
題目已經說每回合可以往右移動一格，或 往下移動一格。
起點在左上角，終點在右下角。
也就是說，假如我現在當下在(x, y)，可以從左邊一格走過來，或上方一格走過來。
走到(x, y)的最小成本
= DP[x, y] = DP[y][x]
= (x, y)本身的成本 + 前一步的最小成本
= grid[x, y] + min{ 前一步的可能情況 }
= grid[x, y] + min{ 走到左邊一格的最小成本， 走到上方一格的最小成本}
= grid[y][x] + min{ DP[y][x-1], DP[y-1][x] } 傳統的陣列表示法
Reference
[1] Minimum Path Sum - LeetCode
回到DP特訓班目錄 和 學習路徑
你可能也想看
