120. Triangle

Question

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

• <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

---

Approach

Naive solution is to start from the top of the triangle, and iterate through to the bottom while look for the smallest element. However, the minimum path sum might not necessarily be the smallest element on each level.

(In Place Bottom-Up)

1. Iterate from the second last level of the triangle, and move upwards. Because we will be computing the level below in each iterations.
2. For each level of the triangle, iterate through all the elements.
3. Update the current triangle value to the minimum between the ith and i+1th element on the level below.
4. So that when we slowly move upwards, the elements are always the minimum sum of the previous levels.
5. Finally when we reach the top of the triangle, it is the smallest sum path.

Solution

class Solution {
public:    
    int minimumTotal(vector<vector<int>>& triangle) {
        //Iterate from the second last level of triangle onwards, because we will be computing the level below in each iterations.
       for(int lv = triangle.size()-2; lv >= 0; lv--){
           //the size of each triangle levels is the level + 1
           //e.g. 0th level has 1 element, 1st level has 2 elements
           for(int i = 0; i <= lv; i++){
               //Update the current triangle value with the current value + the minimum value from below
               triangle[lv][i] += min(triangle[lv+1][i],triangle[lv+1][i+1]);
           }
       }
        //When we reach the top, it will be the smallest sum path
        return triangle[0][0];
    }
};