Thought Process

This was my first interaction with dynamic programming, what I did was go down the triangle and continuously updated each cell with the maximum path length to get there.

I created a function that goes as follows: There is a double nested loop, first loop goes through the rows, i, second loop goes through the elements of each row, j.

1. If the second loop is equal to the first element of the row, that is j = 0, then there is only one path, and thats from the first element of the row above it. So we update triangle[i][j] += triangle[i-1][j]

2. If the second loop is equal to the last element of the row, that is j = len(i) -1, then there is only one path, and thats from the last element of the row above it. So we update triangle[i][j] += triangle[i-1][j-1]

3. Otherwise, there are 2 possible paths. For example after the first iteration of the algorithm the second row will be [75+95, 75+64] = [170, 139], in the next row when deciding what path to take for cell [2][1] (number 47) we must take the maximum of the 2 paths. So we update triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])

At the end the last row will contain the the maximum total to get to each cell, so we just need to return the maximum of the last row!

If you are looking to make sure you understand how this works, try to create the same algorithm except going from the bottom of the triangle to top, then the answer should simply be the first cell