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

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

 

         分析：

             动态规划走起    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)

输出结果：

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