/ Data Structure and Algorithms  

Leetcode 120. Triangle

Question



From current layer can only choose two adjacent elements to walk down. For example, the third layer of 5, we can only choose the fourth layer of 1 and 8, starting from the top. Take a path to the bottom with the smallest sum.

Solution

We can construct the result from top to down, get the possible minimum at a specific positon. Lastly the minimum in the last is the answer we want to get.

There are two options to get to the current position. Choose a smaller one and add the number at the current position.

The point to note is that the left and right borders need to be considered separately, because there is only one position to reach the left and right borders.

We are updating layer by layer, and updating the current layer only requires the information of the previous layer, so we do not need a two-dimensional array, only a one-dimensional array.

E.g

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    [2],
   [3, 4],
  [6, 5, 7],
[4, 1, 8, 3]
     
Update 2-nd layer:
     [2],
   [5, 6],
  [6, 5, 7],
[4, 1, 8, 3]   

Update 3-rd layer:
      [2],
     [5, 6],
  [11, 10, 13],
[4,  1,   8,  3] 

Update last layer:
      [2],
     [5, 6],
  [11, 10, 13],
[15, 11, 18, 16]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int minimumTotal(List<List<Integer>> triangle) {
    List<Integer> previousRow = triangle.get(0);

    // loop every row
    for (int row = 1; row < triangle.size(); row++) {
        List<Integer> temp = new ArrayList<>();

        // loop elements in the row
        for (int i = 0; i < triangle.get(row).size(); i++) {
            // current element
            int elementCurrent = triangle.get(row).get(i);

            // first or last element, add current one with previous row adjacent elements
            if (i == 0) {
                temp.add(elementCurrent + previousRow.get(i));
            } else if (i == triangle.get(row).size() - 1) {
                temp.add(elementCurrent + previousRow.get(previousRow.size() - 1));
            } else {
                temp.add(Math.min(elementCurrent + previousRow.get(i - 1), elementCurrent + previousRow.get(i)));
            }
        }

        previousRow.clear();
        previousRow.addAll(temp);
    }

    // now previous row is the last row
    // sort and find the minimum one
    Collections.sort(previousRow);
    return previousRow.get(0);
}