The problem description is here. For a given triangle you have to find the path with the maximum path. Given an input triangle :
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
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
3
10 7
12 14 13
9 5 9 3
3
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
2 grid, there are 6 routes (without backtracking) to the bottom right corner.
, the number of digits in 
is asymptotic to 
. As a consequence, for every integer d > 1 there are either 4 or 5 Fibonacci numbers with d decimal digits.