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

'''
解题思路：
动态规划算法
dp[i][j]定义为：从左上角到当前位置的最短路径，m[i][j]当前位置上的路径值，
核心迭代公式为，
dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + m[i][j]
即，到当前位置的最短路径 = 从上和从左方向来的路径的最小值 + 当前位置上的路径值
#=============================================================================================
'''
#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix ):
        # write code here
        m = matrix
        r = len(m)
        c = len(m[0])
        #print(r,c)

        dp = [[0]*c for _ in range(r)]
        dp[0][0] = m[0][0]
        for i in range(r):
            for j in range(c):
                if (i==0 and j>0):
                    dp[i][j] = dp[i][j-1] + m[i][j]
                elif (j==0 and i>0):
                    dp[i][j] = dp[i-1][j] + m[i][j]
                else:
                    dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + m[i][j]

        #for i in dp:
        #    print(i)
        return dp[-1][-1]