Understanding the Problem

There is a pyramid given with the length of n. From the bottom to top, the length of the floor is narrowed by 1.

# input
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

# output
11

# visualised triangle
   2
  3 4
 6 5 7
4 1 8 3

Each floor’s path is only connected to the adjacent path of the next floor, meaning it can go from the bottom 1→6→3→2, but it cannot go 3→6→3→2 as 3 and 6 are not adjacent.

Approach

Choosing the right algorithm is the key. I chose the hard way to solve the problem, which I decided to check every possible way to get the summed value by looping all paths. In the end it turn out to be not successful though.

I had the help from my girlfriend about the algorithm. She suggested I choose DP(dynamic programming) calculating it with bottom-up way. DP may be referred to as small scale calculation and use the results from the small scales to solve the whole. There are things to consider before kicking off.

1. Start from the bottom, from the 2nd level of the floor

2. Each path has the two possible ways from the previous paths

3. Get the lower number of the previous two numbers, then sum it with the current number to be used on the next floor

Solution

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        total_len = len(triangle)

        if total_len == 1:
            return triangle[0][0]

        for i in range(total_len - 2, -1, -1):
            for j in range(len(triangle[i])):
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
        return triangle[0][0]

• The loop starts from the bottom, which has to start to loop backwards in the first for loop. then the next loop goes through the numbers in the current floor.

• Check the lower level of the floor with the two passible paths, which are min(triangle[i+1][j], triangle[i+1][j+1]) and the lower number will be summed with triangle[i][j].

This process is run until the triangle[0][0].

Reflection

My girlfriend again says I should look into the answer and learn from the other’s codes instead of getting stuck for hours. I agree with her but it gives me the feeling of defeated when I have to see the solution and hints. Anyways thanks to her help, I get the idea of DP algorithm.