Triagle [dp]

120.Triangle

Array

Dynamic Programming

Problem Statement:

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.

Example:

Input:

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

→

Output:

11

Algorithm:

1. Create DP array size of triangle height
2. Initialize with bottom row values
3. Work bottom-up, calculating min path
4. Each cell stores min path to bottom

Complexity:

Time: O(n²) | Space: O(n) where n is triangle height

Java Solution:

public int minimumTotal(ListInteger>> triangle) {
    // Create dp array with size of triangle height
    int[] dp = new int[triangle.size()];
    
    // Get the bottom row for initialization
    List<Integer> last = triangle.get(dp.length - 1);
    
    // Initialize dp array with bottom row values
    for (int i = 0; i < dp.length; i++) {
        dp[i] = last.get(i);
    }
    
    // Start from second to last row and move up
    for (int i = triangle.size() - 2; i >= 0; i--) {
        List<Integer> currList = triangle.get(i);

        // For each number in current row
        for (int j = 0; j < currList.size(); j++) {
            // Choose minimum of two possible paths and add current value
            dp[j] = Math.min(dp[j], dp[j + 1]) + currList.get(j);
        }
    }
    
    // Top element now contains minimum path sum
    return dp[0];
}

Python Solution:

def minimumTotal(self, triangle: List[List[int]]) -> int:
    # Create and initialize dp array with bottom row
    dp = triangle[-1].copy()
    
    # Start from second to last row
    for i in range(len(triangle) - 2, -1, -1):
        # For each number in current row
        for j in range(len(triangle[i])):
            # Choose minimum path and add current value
            dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
    
    # Top element contains minimum path sum
    return dp[0]

C++ Solution:

class Solution {
public:
    int minimumTotal(vectorint>>& triangle) {
        // Get height of triangle
        int n = triangle.size();
        
        // Create dp array with bottom row
        vector<int> dp(triangle[n-1]);
        
        // Start from second to last row
        for(int i = n-2; i >= 0; i--) {
            // For each number in current row
            for(int j = 0; j <= i; j++) {
                // Update with minimum path sum
                dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
            }
        }
        
        // Return minimum path sum from top
        return dp[0];
    }
};