64. Minimum Path Sum
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.
Example:
Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
思路：
题目意思是给一个网格，找出左上角到右下角最短路径和，和62、63、120题很像，都是经典dp最值问题，子问题就是走到当前位置从哪个方向过来的数值最小。
代码：
go：
代码语言：javascript复制// time: O(n^2), space: O(n^2)
/*func minPathSum(grid [][]int) int {
if grid == nil {return 0}
m := len(grid)
n := len(grid[0])
dp := make([][]int, m)
for i := 0; i < m; i {
dp[i] = make([]int, n)
}
for i := 0; i < m; i {
for j := 0; j < n; j {
if i == 0 && j != 0{
dp[i][j] = dp[i][j-1] grid[i][j]
} else if i != 0 && j == 0 {
dp[i][j] = dp[i-1][j] grid[i][j]
} else if i == 0 && j == 0 {
dp[i][j] = grid[i][j]
} else {
dp[i][j] = min(dp[i][j-1] grid[i][j], dp[i-1][j] grid[i][j])
}
}
}
return dp[m - 1][n - 1]
}*/
// time: O(n^2), space: O(1)
func minPathSum(grid [][]int) int {
if grid == nil {return 0}
m := len(grid)
n := len(grid[0])
for i := 0; i < m; i {
for j := 0; j < n; j {
if i == 0 && j != 0{
grid[i][j] = grid[i][j-1]
} else if i != 0 && j == 0 {
grid[i][j] = grid[i-1][j]
} else if i == 0 && j == 0 {
grid[i][j] = grid[i][j]
} else {
grid[i][j] = min(grid[i][j-1] grid[i][j], grid[i-1][j] grid[i][j])
}
}
}
return grid[m - 1][n - 1]
}
func min (i, j int) int {
if i < j {
return i
}
return j
}```
