与第18题和第67题类似，这是个简单的动态规划问题。
记$a_{i,j}$为矩阵中第i行第j列（从0开始计数）的元素，并令$b_{i,j}$为从矩阵左上方到$a_{i,j}$处的最小路径和，则有
$$b_{i,j}=min(b_{i-1,j},b_{i,j-1})+a_{i,j},\quad i,j>0$$
以及边界条件
$$b_{0,j}=b_{0,j-1}+a_{0,j}, \quad b_{i,0}=b_{i-1,0}+a_{i,0}, \quad b_{0,0}=a_{0,0}.$$
递推即得结果$427337$。
a=[]
with open("081_matrix.txt") as f:
for line in f:
a.append([int(i) for i in line.split(",")])
b=[[0 for j in range(80)] for i in range(80)]
b[0][0]=a[0][0]
for i in range(1,80):
b[0][i]=b[0][i-1]+a[0][i]
b[i][0]=b[i-1][0]+a[i][0]
for i in range(1,80):
for j in range(1,80):
b[i][j]=min(b[i-1][j],b[i][j-1])+a[i][j]
print b[-1][-1]
|
