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

桃扇骨 2022-03-02 01:11 170阅读 0赞

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

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

###          分析： ###

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

### 输出结果： ###

![20190319125053558.png][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70]: /images/20220302/a827be35ac314258b312bc9d7083d853.png
[20190319125053558.png]: /images/20220302/656a4563bf774edfb075df6a34c274bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 1]: /images/20220302/98bc79e13e0845ef87ee7b708a246e0f.png