给定一个包含非负整数的 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
}
}
