64. Minimum Path Sum

从一个矩阵的左上角出发到右下角，只能向右或向下走，找出哪一条路径上的数字之和最小。

思路：动态规划, 需要注意先计算最上和最右的行和列，状态转移方程： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # 6 star 动态规划, 需要注意先计算最上和最右的行和列
        # 状态转移方程： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        m, n = len(grid), len(grid[0])
        dp = [[0 for _ in range(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 j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func minPathSum(grid [][]int) int {
	rows := len(grid[0])
	cols := len(grid)
	dp := make([][]int, cols)
	for c:=0; c<cols;c++ {
		dp[c] = make([]int, rows)  //初始化二维切片
	}
	dp[0][0] = grid[0][0]

	for index, val := range grid[0][1:] {
		dp[0][index+1] = dp[0][index] + val
	}
	for idx:=1; idx<cols; idx++ {
		dp[idx][0] = dp[idx-1][0] + grid[idx][0]
	}
	for i:=1; i < cols; i++ {
		for j:=1; j<rows; j++ {
			if dp[i-1][j] > dp[i][j-1] {
				dp[i][j] = dp[i][j-1] + grid[i][j]
			} else {
				dp[i][j] = dp[i-1][j] + grid[i][j]
			}
		}
	}
	return dp[cols-1][rows-1]

}