题解 | #矩阵的最小路径和#

还是矩阵动态规划，仍然是分析点 （i,j），只能通过（i-1,j)下移或（i,j-1)右移到达。那么令dp（i,j)为到达（ij）最短的路径，有如下关系：
dp(i,j) = min( dp(i, j-1), dp(i-1, j) ) + P(i, j)
其中P(i, j)为点(i,j)的值。
这核心的关系搞清楚了，再看初始条件。右上左下两条边，最短路径都是一条线（只能向右或向下移动！！！），累加计算出dp(0, x) 和 dp(x, 0)

# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix ):
        # write code here
        m = len(matrix)
        n = len(matrix[0])
        for i in range(1, n):
            matrix[0][i] += matrix[0][i-1]

        for i in range(1, m):
            matrix[i][0] += matrix[i-1][0]

        for i in range(1, m):
            for j in range(1, n):
                matrix[i][j] += min(matrix[i][j-1], matrix[i-1][j])
        print(matrix)
        return matrix[-1][-1]