USACO Number Triangle Problem

NUMTRI problem solved with dynamic programming¶

https://stackoverflow.com/questions/16750470/usaco-number-triangle

In [1]:

fin = open ('numtri.in', 'r')
fout = open ('numtri.out', 'w')

N = int(fin.readline().strip())
arow = []
triangle = [[]]*N

for i in range(N):
    arow =  list(map(int, fin.readline().split()))
    triangle[i] = arow
    print(arow)
    
print("\n",triangle)

[7]
[3, 8]
[8, 1, 0]
[2, 7, 4, 4]
[4, 5, 2, 6, 5]

 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

In [2]:

# overwrite the triangle data structure with the dynamic programming solution 
if N > 1: 
    for i in range(N-2,-1,-1):
        for j in range(i+1):
            triangle[i][j] += max(triangle[i+1][j],triangle[i+1][j+1])

print(triangle)

[[30], [23, 21], [20, 13, 10], [7, 12, 10, 10], [4, 5, 2, 6, 5]]

In [3]:

# the final solution is the apex of the triangle
print(triangle[0][0])
fout.write(str(triangle[0][0]) + '\n')
fout.close()

30