Problem 81 – Project Euler

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 and is equal to 2427.

**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**

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.

Have a look at my article about Manhattan Tourist Problem. This problem can be solved using Dynamic Programming.

# Problem 81 of Project Euler
Manhattan = [[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]]
Manhattan[0][0] = 131
# Compute the Horizontal end of each block total path i.e first row
for row in range(1, 5):
Manhattan[row][0] = Manhattan[row-1][0] + Manhattan[row][0]
# Compute the Vertical end of each block total path i.e first column
for col in range(1, 5):
Manhattan[0][col] = Manhattan[0][col-1] + Manhattan[0][col]
# Then fill in the rest of the table.
for row in range(1, 5):
for col in range(1, 5):
Manhattan[row][col] = min(Manhattan[row-1][col] + Manhattan[row][col], Manhattan[row][col-1] + Manhattan[row][col])
print "The Minumum possible path :", Manhattan[4][4]

OUTPUT:

labuser@ubuntu:~$ python manhattan.py

The Minumum possible path : 2427

Since the Algorithm run time is O( nxm) for a nxm matrix so for 80×80 input matrix this algo would take O(n^{2}) time.

### Like this:

Like Loading...

*Related*