3
7 4
2 4 6
9 5 9 3
We can compute the maximum sum path using 2 approaches:
Solution 1 : bottom-up. Build maximum path from bottom. From the next-to-last row, up to the first, add the maximum corresponding sub-triangle. So the initial triangle becomes iteratively:
3
7 4
11 13 15
9 5 9 3
3
20 19
11 13 15
9 5 9 3
23
20 19
11 13 15
9 5 9 3
So the maximum sum is 23, and the maximum path
3
7 4
2 4 6
9 5 9 3
7 4
2 4 6
9 5 9 3
Solution 2: same result is obtained with a top-down approach. Starting from the second row, compute the maximum-sum path to every element. So the initial triangle becomes iteratively:
3
10 7
2 4 6
9 5 9 3
10 7
2 4 6
9 5 9 3
3
10 7
12 14 13
9 5 9 3
10 7
12 14 13
9 5 9 3
3
10 7
12 14 13
21 19 23 16
10 7
12 14 13
21 19 23 16
We get same result for the maximum sum.
Simple python Implementation for the bottom-up solution:
def get_numbers(): #lines = open("tri_small.txt", "r") lines = open("tri.txt", "r") listOfRows = [] for line in lines: currRow = [int(x) for x in line.split()] listOfRows.append(currRow) return listOfRows def solve(): row_list = get_numbers() length = len(row_list) for i in xrange(length-2, -1, -1) : len_row = len(row_list[i]) for j in range(0, len_row) : row_list[i][j] += max(row_list[i+1][j], row_list[i+1][j+1]) print row_list[0] return 0
No comments:
Post a Comment