在如下的$5\times 5$矩阵中，从最左边的列中任意一格出发，始终只向右、向上或向下移动，到最右边的列任意一格结束的最小路径和为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中包含了一个$80 \times 80$的矩阵，求从该矩阵最左边的列中任意一格出发，始终只向右、向上或向下移动，到最右边的列任意一格结束的最小路径和。

注意：本题是第81题的升级版。

本题难度:

解答

与第81题类似，若$b(i,j)$是到第i行第j列为止的最小路径和，则 $$b(i,j)=min_kb(i-1,k)+d(i-1,k,i,j),$$ 其中$d(i-1,k,i,j)$是从$(i-1,k)$先向右一格再向上或向下到达$(i,j)$的路径（若先向上则显然直接从$(i-1,k-1)$出发路径和更小所以第一步只考虑向右），结果是$260324$。

a=[]

with open("082_matrix.txt") as f:
    for line in f:
        a.append([int(i) for i in line.split(",")])

b=[[a[i][j] if j==0 else -1 for j in range(80)] for i in range(80)]

for j in range(1,80):
    for i in range(80):
        b[i][j]=min(b[k][j-1]+(sum(a[x][j] for x in range(i,k+1)) if k>i else sum(a[x][j] for x in range(k,i+1))) for k in range(80))
        
print min(b[i][-1] for i in range(80))