矩形从左上角到右下角找最短路

题目： 如下图：从起点出发，只能想右或者向下走，然后走到终点。。方框里面的数值代表代价，我们要找一条代价比较小的路径。。怎样做呢？快去想想。。

分析：

动态规划走起 i 代表行， j 代表列，我们走一步，累加一步，然后进行选择。

下面分情况：

当 i = 0 （也就是第一行）：我们如果走这条路，每走一步，路径累加。所有就有下式子：

m[0][j] = m[0][j-1] + m[0][j] 就是路径的累加

当 j = 0 （也就是第一列）：我们从这条路走，每走一步，也进行累加

m[i][0] = m[i-1][0] + m[i][0]

当i != 0 并且 j != 0 时，我们就要找从上面下来走这里好，还是从左边过来走这里好？显然是谁小，找谁。。这样代价就小呀，如下式：

m[i][j] = max(m[i-1][j] , m[i][j-1]) + m[i][j]

打印路径：我们刚才每就按一个点，我们都会标记此点的计算是从哪个方向来的（上或者左）。。现在打印路径，我们从右下边的那个元素开始，如果标记向上，我们就先上，向左，我们就向左。。直至到起点。。

代码实现：

def short_path(mat):
    i = len(mat)    # 行数
    j = len(mat[0])  # 列数
    # 建立一个标志矩阵  代表着我们当前往哪里走
    sign = [[None for k in range(j)] for m in range(i)]
    sign[0][0] = '起点'
    for k in range(1, j):
        mat[0][k] += mat[0][k-1]
        sign[0][k] = '向左'
    for m in range(1, i):
        mat[m][0] += mat[m-1][0]
        sign[m][0] = '向上'
    for k in range(1, j):
        for m in range(1, i):
            temp = min(mat[m-1][k], mat[m][k-1])
            if temp == mat[m-1][k]:
                sign[m][k] = '向上'
            if temp == mat[m][k-1]:

                sign[m][k] = '向左'
            mat[m][k] += temp
    for item in sign:
        print(item)

    return mat, sign

def print_path(sign):

    path = []
    i = len(sign) -1
    j = len(sign[0])-1
    while i > 0 and j > 0:
        if sign[i][j] == '向左':
            j -= 1
            path.append('向左')
        if sign[i][j] == '向上':
            i -= 1
            path.append('向上')
    path.append('起点')

    return path

if __name__ == '__main__':
    matrix = [[2, 3, 1, 4, 4],
              [2, 1, 4, 5, 3],
              [3, 0, 2, 3, 6],
              [4, 3, 2, 0, 8],
              [4, 2, 0, 2, 1]]
    mat, sign = short_path(matrix)

    # 打印路径
    path = print_path(sign)
    print("从终点会起点的路径:", path)

输出结果：

我们在按照打印的路径画出来

第十天：《LeetCode一天一例》-----矩形从左上角到右下角找最短路（python实现）

矩形从左上角到右下角找最短路

分析：

代码实现：

输出结果：