120. Triangle

Description

Given a triangle array, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Intuition

The problem can be broken down into simpler subproblems, making it a good candidate for dynamic programming. By starting from the bottom of the triangle and working upwards, we can calculate the minimum path sum for each element, ultimately finding the minimum path sum from the top of the triangle.

Approach

1. Initialization: - Determine the size n of the triangle. - Create a 2D list dp of size n x n initialized with a large value (float('inf') in Python).
2. Recursive Function with Memoization: - Define a helper function f(i, j) that returns the minimum path sum starting at triangle[i][j]. - Base Case: If i is the last row, return the value at triangle[i][j]. - Memoization: If dp[i][j] is not float('inf'), return the stored value to avoid redundant calculations. - Compute the minimum path sum for the current position by considering both the path going directly down and the path going diagonally down-right. - Store the computed minimum path sum in dp[i][j].
3. Return the Result: - Call the helper function starting from the top of the triangle (f(0, 0)) and return the result.

Complexity

Time Complexity:

O(n^2), where n is the number of rows in the triangle. This is because each element in the triangle is processed once, and each recursive call is memoized.

Space Complexity:

O(n^2), which is the space required for the 2D dp array to store the minimum path sums for each element.

Code

C++

class Solution {
public:
    int minimumTotal(vector>& triangle) {
        int n = triangle.size();
        vector> dp(n, vector(n, INT_MAX));

        function f = [&](int i, int j) -> int {
            if (i == n - 1) {
                return triangle[i][j];
            }
            if (dp[i][j] != INT_MAX) {
                return dp[i][j];
            }
            int down = triangle[i][j] + f(i + 1, j);
            int diag = triangle[i][j] + f(i + 1, j + 1);
            return dp[i][j] = min(down, diag);
        };

        return f(0, 0);
    }
};

Python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [[float('inf')] * n for _ in range(n)]

        def f(i: int, j: int) -> int:
            if i == n - 1:
                return triangle[i][j]
            if dp[i][j] != float('inf'):
                return dp[i][j]
            down = triangle[i][j] + f(i + 1, j)
            diag = triangle[i][j] + f(i + 1, j + 1)
            dp[i][j] = min(down, diag)
            return dp[i][j]

        return f(0, 0)

Java

class Solution {
    public int minimumTotal(List> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        
        // Initialize the dp array with a large value
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        // Recursive function with memoization
        return f(triangle, 0, 0, dp);
    }
    private int f(List> triangle, int i, int j, int[][] dp) {
        int n = triangle.size();
        if (i == n - 1) {
            return triangle.get(i).get(j);
        }
        if (dp[i][j] != Integer.MAX_VALUE) {
            return dp[i][j];
        }
        int down = triangle.get(i).get(j) + f(triangle, i + 1, j, dp);
        int diag = triangle.get(i).get(j) + f(triangle, i + 1, j + 1, dp);
        dp[i][j] = Math.min(down, diag);
        return dp[i][j];
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        List> triangle = new ArrayList<>();
        triangle.add(List.of(2));
        triangle.add(List.of(3, 4));
        triangle.add(List.of(6, 5, 7));
        triangle.add(List.of(4, 1, 8, 3));
        System.out.println(solution.minimumTotal(triangle)); // Output: 11
    }
}

JavaScript

var minimumTotal = function(triangle) {

    let n = triangle.length;
    let dp = Array(n).fill(Number.MAX_VALUE).map(()=> Array(n).fill(Number.MAX_VALUE));
    //let min = Number.MAX_VALUE;
    function f(i, j){

        if(i == n-1){return triangle[i][j];}
        if(dp[i][j] != Number.MAX_VALUE) return dp[i][j];
        let down = triangle[i][j] + f(i+1, j);
        
        let diag = triangle[i][j] + f(i+1, j+1);
        return dp[i][j] = Math.min(down, diag);
    }
    return f(0, 0);
};