64. Minimum Path Sum

题目

给定一个由非负数i填充的 m*n 网格，找到一条从左上角到右下角的路径，使得所有数字和最小。

解析

要求到 grid[m-1][n-1] 的最小值，可以转化为到 min(grid[m-2][n-1] +grid[m-1][n-1],grid[m-1][n-2]+grid[m-1][n-2])

伪代码

for i<col
  grid[0][i] +=grid[0][i-1]
for i<row
  grid[i][0] +=grid[i-1][0]
for i<row
  for j<col
    grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[row-1][col-1]

代码

func minPathSum(grid [][]int) int {
    row := len(grid)
    col := len(grid[0])
    for i:=1;i<col;i++ {
        grid[0][i] += grid[0][i-1]
    }
    for i:=1;i<row;i++ {
        grid[i][0] += grid[i-1][0]
    }
    for i:=1;i<row;i++ {
        for j:=1;j<col;j++ {
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        }
    }
    return grid[row-1][col-1]
}

func min(a,b int) int {
    if a < b {
        return a
    }
    return b
}

image.png