# Dynamic Programming - 64. Minimum Path Sum

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.

go：

``````// 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
}```
``````

Nothing just happens, it's all part of a plan.