Problem Overview

You are given a triangle array — each row has one more element than the previous one.
Starting from the top, you can move to adjacent numbers in the next row.
Your task is to find the minimum path sum from the top to the bottom.

At every step, you can move:

• from triangle[i][j] → triangle[i+1][j] (same index)

• or → triangle[i+1][j+1] (next index)

Example

Triangle:

       6
     3   6
   9   12  -2
 12   4   11  -4

We need to find the smallest path sum from the top to the last row.

Approach 1: Greedy Algorithm

The greedy idea is to always choose the smallest number in the next row at each step.
For example:

• Start at 6

• Choose the smaller of (3, 6) → pick 3

• From 3, choose the smaller of (9, 12) → pick 9

• From 9, choose the smaller of (12, 4) → pick 4

Path: 6 → 3 → 9 → 4
Sum = 22

Problem:
This doesn’t always work, because a local minimum might lead to a bad total later.
The greedy method doesn’t guarantee the globally minimum path.

Approach 2: Generate All Possible Paths

We can try every possible path from top to bottom using recursion or backtracking.
At each level, we explore both possible directions and keep the smallest sum.

This method guarantees the correct answer but is very slow, because it tries all paths.
If there are n rows, the number of possible paths is 2^(n-1).
So it works only for small triangles.

Example (conceptually):

Try all paths:
6 → 3 → 9 → 12
6 → 3 → 9 → 4
6 → 3 → 12 → 4
6 → 6 → -2 → -4
...
Take the minimum total.

It’s correct but inefficient.

Approach 3: Bottom-Up Dynamic Programming

This is the most efficient and elegant solution.

We start from the bottom row and move upward, combining results as we go.
For each cell, we calculate the minimum total path from that cell to the bottom.

We use the formula:

triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])

This means:

• The cost of reaching the bottom from triangle[i][j]
  = current value + minimum of the two possible downward paths.

When we reach the top, triangle[0][0] will contain the minimum total path sum.

Step-by-Step on the Example

Triangle before processing:

       6
     3   6
   9   12  -2
 12   4   11  -4

Start from the second-last row and move up.

Row 3 (bottom): [12, 4, 11, -4]

Row 2:

triangle[2][0] = 9 + min(12, 4) = 9 + 4 = 13  
triangle[2][1] = 12 + min(4, 11) = 12 + 4 = 16  
triangle[2][2] = -2 + min(11, -4) = -2 + (-4) = -6  

Now Row 2 becomes [13, 16, -6]

Row 1:

triangle[1][0] = 3 + min(13, 16) = 3 + 13 = 16  
triangle[1][1] = 6 + min(16, -6) = 6 + (-6) = 0  

Now Row 1 becomes [16, 0]

Row 0:

triangle[0][0] = 6 + min(16, 0) = 6 + 0 = 6  

Final result = 6

So the minimum path sum is 6.

Time and Space Complexity

• Time Complexity: O(n²), because we process all cells once.

• Space Complexity: O(1), because we reuse the same triangle array (no extra space needed).

Final Code

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle[i].size(); j++) {
                triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }
        return triangle[0][0];
    }
};

Summary

• Greedy: fast but incorrect in many cases.

• All paths: correct but very slow.

• Dynamic Programming (bottom-up): optimal in both correctness and efficiency.