从一个矩阵的左上角出发到右下角，只能向右或向下走，找出哪一条路径上的数字之和最小。
思路：动态规划, 需要注意先计算最上和最右的行和列，状态转移方程： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
class Solution:
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# 6 star 动态规划, 需要注意先计算最上和最右的行和列
# 状态转移方程： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
m, n = len(grid), len(grid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]Go:
func minPathSum(grid [][]int) int {
rows := len(grid[0])
cols := len(grid)
dp := make([][]int, cols)
for c:=0; c<cols;c++ {
dp[c] = make([]int, rows) //初始化二维切片
}
dp[0][0] = grid[0][0]
for index, val := range grid[0][1:] {
dp[0][index+1] = dp[0][index] + val
}
for idx:=1; idx<cols; idx++ {
dp[idx][0] = dp[idx-1][0] + grid[idx][0]
}
for i:=1; i < cols; i++ {
for j:=1; j<rows; j++ {
if dp[i-1][j] > dp[i][j-1] {
dp[i][j] = dp[i][j-1] + grid[i][j]
} else {
dp[i][j] = dp[i-1][j] + grid[i][j]
}
}
}
return dp[cols-1][rows-1]
}