64.最小路径和

解题思路

  1. 动态规划，创建一个二维数组dp[i][j],代表(0,0) 到 (i,j) 的最小路径和
  2. dp 初始化，首行首列遍历填充
  3. 状态转移方程 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j], 即(i,j)左边，上边的最小值 + 自身

代码实现

func minPathSum(grid [][]int) int {
     if len(grid) == 0 || len(grid[0]) == 0 {
          return 0
     }
     m, n := len(grid), len(grid[0])
     dp := make([][]int, m)
     for i := range dp {
          dp[i] = make([]int, n)
     }
     dp[0][0] = grid[0][0]
     for i := 1; i < m; i++ {
          dp[i][0] = dp[i-1][0] + grid[i][0]
     }
     
     for j := 1; j < n; j++ {
          dp[0][j] = dp[0][j-1] + grid[0][j]
     }
     
     for i := 1; i < m; i++ {
          for j := 1; j < n; j++ {
              dp[i][j] = int(math.Min(float64(dp[i-1][j]), float64(dp[i][j-1]))) + grid[i][j]
          }
     }
     
     return dp[m-1][n-1]
}