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.``````

Solution:

``````func minPathSum(grid [][]int) int {
lenX := len(grid)
if lenX == 0 {return 0}
lenY := len(grid[0])

dp := make([][]int, 2) //compress to 2 row dp
dp[0] = make([]int, lenY+1 ) //dummy node
dp[1] = make([]int, lenY+1 )

for i := 0; i < lenX ; i++ {
for j:= 0; j < lenY; j++ {
dx, dy := i+1, j+1
switch {
case i == 0 && j == 0:
dp[dx%2][dy] = grid[i][j]
case i == 0 :
dp[dx%2][dy] = dp[dx%2][dy-1] + grid[i][j]
case j == 0 :
dp[dx%2][dy] = dp[(dx-1)%2][dy] + grid[i][j]
default:
dp[dx%2][dy] = min(dp[(dx-1)%2][dy],dp[dx%2][dy-1]) + grid[i][j]
}

}
}
return dp[(lenX)%2][lenY]

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