082. 路径数字之和:三个方向(Path sum: three ways)

在下面这个五乘五的数字矩阵中,从最左列的任何一格出发,可以向右、上、下三个方向走,到达最右列的任何一格,这其中所经过数字之和的最小值是994,这些数字都已用红色标示。

$$ \begin{pmatrix} 131 & 673 & \color{red}{234} & \color{red}{103} & \color{red}{18}\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & 746 & 422 & 111\\ 537 & 699 & 497 & 121 & 956\\ 805 & 732 & 524 & 37 & 331 \end{pmatrix} $$
在文本文件 matrix.txt中有一个八十行八十列的数字矩阵,求从这个矩阵的最左列到最右列所经数字之和的最小值。

注:这道题比第八十一题更具挑战性。

分析:相对于第八十一题,这道题中除可以向右和向下移动外,还可以向上移动,而且出发和到达的单元格不固定,使得这一题的难度大大提升。但在使用的思路方面,还是和第八十一题是类似的,都是动态规划的思想。对于矩阵的每一格,我们记录下到达这个单元格的最小路径和,把它们保存在\(cost\)列表中,然后逐列向右推移最终到达最右一列,然后此时\(cost\)列表的最小值即为题目所求。代码如下:

# time cost = 7.4 ms ± 81.7 µs

def min_path_sum(matrix):
    n = len(matrix)
    cost = [matrix[i][0] for i in range(n)]
    for column in range(1,n):
        cost[0] += matrix[0][column]
        for row in range(1,n):
            cost[row] = min(cost[row], cost[row-1]) + matrix[row][column]
        for row in range(n-2, -1, -1):
            cost[row] = min(cost[row], cost[row+1] + matrix[row][column])
    return min(cost)

def main():
    with open('data/pe082.txt') as f:
        matrix = [[int(x) for x in row.split(',')] for row in f.readlines()]
    return min_path_sum(matrix)