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
}