Project Euler Project 67 – Python

I am doing the Project Euler #67 in Python. My program, which worked for Project 18, does not work for Project 67. Code (excludes the opening of the file and the processing of information):

for i in range(len(temp)):
    list1 = temp[i]
    try:
        list2 = temp[i+1]
        trynum1 = list1[lastinput] + max(list2[lastinput],list2[lastinput+1])
        try:
            trynum2 = list1[lastinput+1] + max(list2[lastinput+1],list2[lastinput+2])
            if trynum1 > trynum2:
                outputlist.append(list1[lastinput])
            else:
                outputlist.append(list1[lastinput+1])
                lastinput += 1
        except IndexError:
            outputlist.append(list1[0])
    except IndexError:
        if list1[lastinput] > list1[lastinput+1]:
            outputlist.append(list1[lastinput])
        else:
            outputlist.append(list1[lastinput+1])

Variables:

temp is the triangle of integers

outputlist is a list which stores the numbers chosen by the program

I know the answer is 7273, but my program finds 6542. I cannot find an error which causes the situation. Please may you help me on it.

Logic

My approach to this program is to find one number (list1[lastinput]) and add it up with the larger number of the two below it (trynum1), compare with the number to the right of the first number (list1[lastinput+1]), adding the larger number of two below it (trynum2). I append the larger one to the output list.

Answer

This approach is logically flawed. When you’re in row 1, you don’t have enough information to know whether moving right or left will lead you to the largest sum, not with only a 2-row lookahead. You would need to look all the way to the bottom to ensure getting the best path.

As others have suggested, start at the bottom and work up. Remember, you don’t need the entire path, just the sum. At each node, add the amount of the better of the two available paths (that’s the score you get in taking that node to the bottom). When you get back to the top, temp[0][0], that number should be your final answer.