Max path triangle

I have a triangle with two-hundred rows, where I have to find the maximum distance to get from the top to the bottom of the triangle.

Here, the shortest distance would be 5+8+4+3=20. The maximum distance would be 5+9+5+9=28.

I have a good idea of the algorithm I want to implement but I am struggling to turn it into code.

My plan is: start at the 2nd to last row, add the maximum of the possible paths from the bottom row, and iterate to the top.

For instance, the above triangle would turn into:

This is vastly more efficient than brute-forcing, but I have two general questions:

Using brute-force, how do I list all the possible paths from top to bottom (can only move to adjacent points)? I tried using this (triangle is the list of lists containing the triangle):
```
points=list(itertools.product(*triangle))  
```
but this contains all possible combinations from each row, not just adjacent members. Project Euler #18 - how to brute force all possible paths in tree-like structure using Python? This somewhat explains a possible approach, but I'd like to use itertools and any other modules (as pythonic as possible)

How would I go about iterating the strategy of adding each maximum from the previous row and iterating to the top? I know I have to implement a nested loop:

for x in triangle:
    for i in x:
        i+=? #<-Not sure if this would even increment it

edit:
what I was thinking was:
triangle[y][x] = max([triangle[y+1][x],triangle[y+1][x+1]])

Solution

It does not use itertools, it is recursive, but I memoize the results, so its still fast...

def memoize(function):
    memo = {}
    def wrapper(*args):
      if args in memo:
        return memo[args]
      else:
        rv = function(*args)
        memo[args] = rv
        return rv
    return wrapper



@memoize
def getmaxofsub(x, y):
    if y  == len(triangle) or x>y: return 0
    #print x, y
    return triangle[y][x] + max(getmaxofsub(x, y+1), getmaxofsub(x+1, y+1))


getmaxofsub(0,0)

I read your algorithm suggestion some more times and your "cumulative triangle" is stored in memoof the memoized decorator, so in the end it is very similar. if you want to prevent that there is big stack during recursive "down calling" through the triangle, you can fill the cache of memoize by calling getmaxofsub() bottom -> up.

for i in reversed(range(len(triangle))):
    getmaxofsub(0, i), getmaxofsub(i//2, i), getmaxofsub(i, i)

print getmaxofsub(0,0)

Edit

getmaxofsub: How does this function work? First you have to know, that you can't divide your triangle in sub triangles. I take your triangle as an example:

That's the complete one. The "coordinates" of the peak are x=0, y=0.

Now I extract the sub triangle of the peak x=0, y=1:

  9
 5 4
9 7 3

or x=1, y=2

 4
7 3

So this is how my algorithm works: The peak of the whole triangle (x=0, y=0) asks its sub triangles (x=0, y=1) and (x=1, y=1), "What is your maximum distance to the ground?" And each of them will ask their sub-triangles and so on… this will go on until the function reaches the ground/y==len(triangle): The ground-entries want to ask their sub triangles, but since their is none of those, they get the answer 0. After each triangle has called their sub triangles, it decides, which one is the greater one, add their own value and return this sum.

So now you see, what is the principle of this algorithm. Those algorithms are called recursive algorithms. You see, a function calling itself is pretty standard… and it works…

So, if you think about this whole algorithm, you would see that a lot of sub-triangles are called several times and they would ask their sub-triangles and so on… But each time they return the same value. That is why I used the memorize-decorator: If a function is called with the same arguments x and y, the decorator returns the last calculated value for those arguments and prevents the time-consuming calculation… It is a simple cache…

That is why this function is as easy to implement as a recursive algorithm and as fast as a iteration...