forked from riobard/project-euler
-
Notifications
You must be signed in to change notification settings - Fork 0
/
081.py
31 lines (24 loc) · 752 Bytes
/
081.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
'''
P0018, P0067, P0081, P0083 are variants of each other.
Dynamic Programming
1) overlapping subproblems
2) optimal substructure
Two approaches:
1) Top-down: memoization
2) Bottom-up:
'''
mat = [[131, 673, 234, 103, 18],
[201, 96, 342, 965, 150],
[630, 803, 746, 422, 111],
[537, 699, 497, 121, 956],
[805, 732, 524, 37, 331]]
mat = [map(int, line.strip().split(',')) for line in open('matrix.txt')]
M = len(mat)-1
from euler import memoized
@memoized
def f(i, j):
if i==j==M: return mat[i][j]
elif i==M: return mat[i][j] + f(i, j+1)
elif j==M: return mat[i][j] + f(i+1, j)
else: return mat[i][j] + min(f(i+1, j), f(i, j+1))
print f(0,0)