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

1.动态规划递归版
g(M)表示从矩阵M[:n][:m]右下角走到左上角的最小路径长度
递归式为：g(A) = min(g(M[:n][:m-1]), g(M[:n-1][:m])) + M[n-1][m-1]
递归基：当矩阵为一行或者一列时，即当n==1或者m=1时，g(M)=sum(M)

    # 动态规划-递归
    def minPathSum(self , matrix ):
        n = len(matrix)
        m = len(matrix[0])
        if n==1:
            sum_ = 0
            for i in range(m):
                sum_ += matrix[0][i]
            return sum_
        if m==1:
            sum_ = 0
            for i in range(n):
                sum_ += matrix[i][0]
            return sum_
        sumDown = self.minPathSum(matrix[:n-1][:m])
        B = [matrix[i][:m-1] for i in range(n)]
        sumRight = self.minPathSum(B)
        return min(sumDown, sumRight) + matrix[0][0]

2.动态规划迭代版
上一版需要很多重复计算，并且递归过程中占用内存大，因而考虑迭代法：颠倒计算方向，将所有子问题列成一张表，从矩阵的左上角出发，依次求出所有项的最小路径长度。
用矩阵A存储各子问题的计算结果，A[i][j]表示从matrix[0][0]出发，到matrix[i][j]的最小路径长度。

    def minPathSum(self , matrix ):
        # write code here
        n = len(matrix)
        m = len(matrix[0])
        A = [[0]*(m) for i in range(n)]
        A[0][0] = matrix[0][0]
        for i in range(1,n):
            A[i][0] = A[i-1][0] + matrix[i][0]
        for j in range(1,m):
            A[0][j] = A[0][j-1] + matrix[0][j]

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