64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

思路:到最右小角的路径有2种情况，一种是从左边往右，一种是从上边往下，我们只要比较这两种路径的大小，取最小即可。
而走到这两个点又有两种情况，即从左边点的左边往右，从左边点的上边往下，如此循环，递归,取最小情况

func minPathSum(grid [][]int) int {
    m := len(grid)
    if m < 0 {
        return 0
    }
    n := len(grid[0])

    // 设x = s(m,n)， 为[0,0]到 [m-1,n-1]点路径的最小值
    // 则 x = min(s(m,n-1), s(m-1,n))
    // 一直递归到 m -1 = 0 或 n-1 = 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] = grid[i][j]
            } else if i == 0 {
                //第0行，每一列的值为前一列值(array数组)加上当前列的值(arr数组)
                dp[i][j] = dp[i][j-1] + grid[i][j]
            } else if j == 0 {
                //第0列，每一行的值为前一行值(array数组)加上当前行的值(arr数组)
                dp[i][j] = dp[i-1][j] + grid[i][j]
            } else {
                //该位置的值为 该位置(array[i][j])的左边和上边值的最小值 加上当前位置的值(arr数组)
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
            }
        }
    }
    return dp[m-1][n-1]
}

func min(a, b int) int {
    if a >= b {
        return b
    } else {
        return a
    }
}