今天是紀錄LeetCode解題的第六十四天

第六十四題題目：Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

給定一個m * n由非負整數組成的grid，找出一條路徑從左上到右下路徑總和值最小
注意：只能往右或往左移動

解題思路

這題和62題也是同個概念(62、63、64都比較類似，可以往前看其他兩篇文章)，我們可以用DP來解，只是現在DP表格裡的數字代表到該格的最少總和值，一樣我們先初始化row = 0、col = 0時的情況，可以知道到該格的最少路徑總和等於前一列(行)DP表格的值加目前格子的數值(dp[0][i] = dp[0][i-1] + grid[0][i])，在62題當中我們推論出轉移方程式為dp[r][c] = dp[r-1][c] + dp[r][c-1]，而這裡則改成判斷這兩個誰最小再加上自己該格的數值，所以轉移方程式為dp[r][c] = min(dp[r-1][c] + grid[r][c],dp[r][c-1] + grid[r][c])

程式碼

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1,m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in range(1,n):
            dp[0][i] = dp[0][i-1] + grid[0][i]
        for r in range(1,m):
            for c in range(1,n):
                dp[r][c] = min(dp[r-1][c] + grid[r][c],dp[r][c-1] + grid[r][c])
        return dp[m-1][n-1]

DP表格(grid = [[1,3,1] , [1,5,1] , [4,2,1]])

• 初始化row = 0、col = 0時，該列(行)的最少總和只要加該格和前一列(行)的值即可
• 當row = 1、col = 1時，路徑總和有1 + 3 + 5 = 9和1 + 1 + 5 = 7，選擇最小的7
• 當row = 1、col = 2時，路徑總和有dp[0][2] = 5和dp[1][1] (剛剛算出來是7) 可以選擇，而dp[0][2]的值比較小，所以加上grid[1][2] = 1的值為最小總和(5 + 1 = 6)