Project Euler 81

发表于 更新于 分类于 本文字数： 1.2k 阅读时长 ≈ 1 分钟

Project Euler 81

题目

Path sum: two ways

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

(131673234103182019634296515063080374642211153769949712195680573252437331)

Find the minimal path sum, in matrix.txt (right click and “Save Link/Target As…”), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

解决方案

本题是一道很明显的动态规划。

令矩阵大小为 n，记录状态 f(i,j)(1≤i,j≤n) 为：当前走到第 i 行第 j 列的数的情况下，可以得到的路径最小和是多少，用 a[i][j] 表示第 i 行第 j 列的数。

那么，可以得到状态转移方程：

f(i,j)={a[i][j]ifi=j=1f(i−1,j)+a[i][j]else ifj=1f(i,j−1)+a[i][j]else ifi=1min(f(i,j−1),f(i−1,j))+a[i][j]else

对于有两种到达方式的状态，无非就是从上的格子走过来，和从左边的格子走过来两种。取这两种方式的较优决策即可。

最后答案为 f(n,n).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a = []
ls = open('p081_matrix.txt', 'r').readlines()
n = len(ls)
f = [[10 ** 10 for x in range(n)] for y in range(n)]
for i in range(n):
    b = [int(x) for x in ls[i][:-1].split(',')]
    a.append(b)

f = [[10 ** 10 for x in range(n + 1)] for y in range(n + 1)]
f[0][1] = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        f[i][j] = min(f[i - 1][j], f[i][j - 1]) + a[i-1][j-1]
print(f[n][n])