矩阵的最小路径和——python

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围: 1 le n,mle 5001≤n,m≤500，矩阵中任意值都满足 0 le a_{i,j} le 1000≤ai,j​≤100

要求：时间复杂度 O(nm)O(nm)

用转移方程可以很方便的解决这个问题：

 def minPathSum(self , matrix ):
        # write code here
        m = len(matrix)
        n = len(matrix[0])
        m=len(matrix)
        dp=[[0 for _ in range(n)]for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i==0 and j==0:
                    dp[i][j]=matrix[0][0]
                elif i==0:
                    dp[i][j]=dp[i][j-1]+matrix[i][j]
                elif j==0:
                    dp[i][j] = dp[i-1][j] + matrix[i][j]
                else:
                    dp[i][j] =min(dp[i - 1][j] ,dp[i ][j-1])  + matrix[i][j]
        return dp[m-1][n-1]