语言：python

思路：1.检验矩阵大小，若n>m,则转置该矩阵（便于后续计算）即matrix = matrixT

2.建立一个代价矩阵，其大小与matrix相等，每个格子的值将代表从该格子出发到终点的最小路径（代价）

3.先从终点开始走，计算包围终点的方格（最内层蓝色方格）的最小代价，计算顺序见标号。 

先计算上边的，在计算左边的，这样的话每个方格在计算自身最小路径值时，到终点的最短路径值都是已知的

比如已经计算了1，2，方格，计算3方格时，由于只能向下或向右走，而3方格右边和下边的方格代价是已知的，

3只要选择最小的方向（1或者2）就可以使得到终点的路径最小

4.当遍历完n x n矩阵时再遍历左侧多余的方格，遍历方向是向上

5.当计算完代价矩阵时，代价矩阵的起始点即是到终点的最短路径代价 

def revermat(data,n,m):
    remat = [[0 for i in range(n)]for j in range(m)]
    for i in range(n):
        for j in range(m):
            remat[j][i] = data[i][j]
    return remat

class Solution:
    def minPathSum(self , matrix ):
        n = len(matrix)
        m = len(matrix[0])
        if n>m:
            matrix = revermat(matrix, n, m)
            temp = n
            n = m
            m = temp
        data2 = [[0 for i in range(m)]for j in range(n)]
        data2[n-1][m-1] = matrix[n-1][m-1]
        for i in range(1,n,1):
            for c in range(m-1,m-i-1,-1):
                if c == m-1:
                    data2[n-1-i][c] = matrix[n-1-i][c]+data2[n-i][c]
                else:
                    data2[n-1-i][c] = min(data2[n-1-i][c+1],data2[n-i][c])+matrix[n-1-i][c]
            for r in range(n-1,n-i-2,-1):
                if r == n-1:
                    data2[r][m-i-1] = matrix[r][m-i-1]+data2[r][m-i]
                else:
                    data2[r][m-i-1] = min(data2[r+1][m-i-1],data2[r][m-i])+matrix[r][m-i-1]
        for j in range(m-n-1,-1,-1):
            for r in range(n-1,-1,-1):
                if r == n-1:
                    data2[r][j] = matrix[r][j] + data2[r][j+1]
                else:
                    data2[r][j] = min(data2[r+1][j],data2[r][j+1])+matrix[r][j]
        return data2[0][0]