text
function findMinPath(row, col):
    // Base case: if we are at the bottom, return the value
    if row == last_row:
        return triangle[row][col]
    
    // Recursive step: explore both paths
    left_path = findMinPath(row + 1, col)
    right_path = findMinPath(row + 1, col + 1)
    
    return triangle[row][col] + min(left_path, right_path)

Complexity Analysis

The time complexity of this brute force solution is O(2^N), where N is the number of rows in the triangle. Since the height of the recursion tree is N and each node branches into two, the number of operations grows exponentially.

Why it Fails

This approach fails due to Time Limit Exceeded (TLE) errors on large inputs. The recursion solves the same sub-problems repeatedly. For example, the node at triangle[2][1] is reached from both triangle[1][0] (going right) and triangle[1][1] (going left). The brute force algorithm recalculates the minimum path starting from triangle[2][1] every time it is reached, leading to massive redundancy.

Core Insight for Triangle

The key intuition is to reverse the direction of thinking. Instead of starting at the top and greedily guessing which path might be best (which doesn't work), or recursively exploring all paths (which is too slow), we start at the bottom.

Consider the second-to-last row. For any element in this row, the minimum path to the bottom is simply the element's value plus the smaller of its two children in the last row. Once we calculate this for every element in the second-to-last row, we can discard the last row entirely. We effectively "collapse" the triangle upward.

By repeating this process, each row inherits the optimal decisions from the row below it. When we finally reach the top element, it will contain the minimum path sum for the entire triangle.

Visual Description: Imagine the triangle as a stack of layers.

1. We look at the bottom-most layer (row N-1). The cost to reach the bottom from here is fixed (the values themselves).
2. Move up to row N-2. For a cell at index i, we look at the two cells below it: dp[i] and dp[i+1]. We take the minimum of these two, add the current cell's value, and update dp[i].
3. This process overwrites the DP state, shrinking the problem size by one row at each step until only dp[0] remains.

Algorithm Strategy: DP - 2D Array (Unique Paths on Grid)

1. State Definition: We need a way to store the minimum path sum from the current row to the bottom. Let dp[i] represent the minimum path sum starting from index i in the current row down to the bottom.
2. Initialization: Initialize the dp array with the values of the last row of the triangle. This is our base case.
3. Iteration: Iterate starting from the second-to-last row up to the top row (row 0).
4. Transition Equation: For each element at index i in the current row r, update the dp array: dp[i] = triangle[r][i] + min(dp[i], dp[i+1]) Here, dp[i] (before update) represents the path going directly down, and dp[i+1] represents the path going down-right.
5. Space Optimization: By modifying the array in place or using a single 1D array of size N (where N is the number of rows), we satisfy the follow-up constraint of O(N) extra space.
6. Result: After processing the top row, dp[0] will hold the global minimum path sum.

Execution Flow

Let's trace the algorithm with triangle = [[2], [3,4], [6,5,7], [4,1,8,3]].

1. Initialize DP Array: Load the last row into our DP table. dp = [4, 1, 8, 3]

2. Process Row 2 ([6, 5, 7]):

   • Index 0 (Value 6): min(dp[0], dp[1]) is min(4, 1) = 1. New dp[0] = 6 + 1 = 7.
   • Index 1 (Value 5): min(dp[1], dp[2]) is min(1, 8) = 1. New dp[1] = 5 + 1 = 6.
   • Index 2 (Value 7): min(dp[2], dp[3]) is min(8, 3) = 3. New dp[2] = 7 + 3 = 10.
   • State: dp = [7, 6, 10, 3] (Index 3 is ignored in future steps).

3. Process Row 1 ([3, 4]):

   • Index 0 (Value 3): min(dp[0], dp[1]) is min(7, 6) = 6. New dp[0] = 3 + 6 = 9.
   • Index 1 (Value 4): min(dp[1], dp[2]) is min(6, 10) = 6. New dp[1] = 4 + 6 = 10.
   • State: dp = [9, 10, 10, 3].

4. Process Row 0 ([2]):

   • Index 0 (Value 2): min(dp[0], dp[1]) is min(9, 10) = 9. New dp[0] = 2 + 9 = 11.
   • State: dp = [11, 10, 10, 3].

5. Return Result: Return dp[0], which is 11.

Proof of Correctness

The correctness relies on the principle of optimality: an optimal path from the top to the bottom must consist of optimal sub-paths.

For any node (r, c), the path to the bottom must go through either (r+1, c) or (r+1, c+1). If we already know the minimum path sums starting from (r+1, c) and (r+1, c+1), the minimum path starting from (r, c) is strictly determined by adding triangle[r][c] to the smaller of those two sums.

Since we compute values from the bottom up, we guarantee that when we process row r, the values for row r+1 are already optimal. Therefore, the value computed for the top element is guaranteed to be the global minimum.

Reference Implementation

C++ Solution for LeetCode 120

cpp
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        // Initialize dp array with the values of the last row
        vector<int> dp = triangle[n - 1];

        // Iterate from the second to last row up to the top
        for (int row = n - 2; row >= 0; --row) {
            for (int i = 0; i <= row; ++i) {
                // Calculate the min path for the current cell
                // by looking at the two possible moves below it
                dp[i] = triangle[row][i] + min(dp[i], dp[i + 1]);
            }
        }

        // The top element now contains the minimum path sum
        return dp[0];
    }
};

Java Solution for LeetCode 120

java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // dp array size matches the number of rows (width of the bottom)
        int[] dp = new int[n];
        
        // Initialize dp with the last row
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }

        // Iterate from second to last row upwards
        for (int row = n - 2; row >= 0; row--) {
            for (int i = 0; i <= row; i++) {
                // Determine the minimum of the two children
                int minChild = Math.min(dp[i], dp[i + 1]);
                // Update dp table with current value + min child
                dp[i] = triangle.get(row).get(i) + minChild;
            }
        }

        return dp[0];
    }
}

Python Solution for LeetCode 120

python
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # Start with the values of the last row
        dp = triangle[-1][:]
        
        # Iterate backwards from the second to last row to the top
        # range(start, stop, step) -> stop is exclusive
        for row in range(len(triangle) - 2, -1, -1):
            for i in range(len(triangle[row])):
                # Update current index with the value of the triangle cell
                # plus the minimum of the two adjacent values from the row below
                dp[i] = triangle[row][i] + min(dp[i], dp[i + 1])
                
        # The first element holds the minimum path sum for the whole triangle
        return dp[0]