46 lines
1.2 KiB
Python
46 lines
1.2 KiB
Python
data = [
|
|
[0, 9, 2, 5, 11, 8],
|
|
[17, 21, 32, 5, 15, 3],
|
|
[2, 2, 3, 8, 1, 5],
|
|
[8, 2, 8, 11, 15, 9],
|
|
[0, 5, 3, 10, 4, 0]
|
|
]
|
|
|
|
max_y = len(data)
|
|
max_x = len(data[0])
|
|
start = (max_y-1, max_x-1)
|
|
|
|
# Table with size of data
|
|
table = [[None for _ in range(max_x)] for _ in range(max_y)]
|
|
|
|
def find_path(y, x):
|
|
# Return bad value for positions which are out of bounds
|
|
if not (0 <= y < max_y and 0 <= x < max_x):
|
|
return (), float('-inf')
|
|
|
|
# Table look up
|
|
if table[y][x] is not None:
|
|
return table[y][x]
|
|
|
|
# End of the recursion is the starting position
|
|
if y == 0 and x == 0:
|
|
res = (((y, x),), data[y][x])
|
|
# Calculate defined recursion on all other existing positions
|
|
else:
|
|
west_path, west_val = find_path(y, x-1)
|
|
north_path, north_val = find_path(y-1, x)
|
|
|
|
# Choose most valuable path to the considered position
|
|
if west_val > north_val:
|
|
res = (west_path + ((y, x),), west_val + data[y][x])
|
|
else:
|
|
res = (north_path + ((y, x),), north_val + data[y][x])
|
|
|
|
# Store most valuable path in the table and return
|
|
table[y][x] = res
|
|
return res
|
|
|
|
path, val = find_path(*start)
|
|
print(f"Val: {val}")
|
|
print(f"Path: {path}")
|