120. Triangle

Time: O(n²)

Space: O(n)

Intuition

Bottom-up DP: starting from the second-to-last row, each cell becomes its value plus the minimum of the two cells below it. After processing all rows, triangle[0][0] holds the answer. Modify in-place or use a 1D dp array.

Algorithm

1For row from n-2 down to 0: for col from 0 to row: triangle[row][col] += min(triangle[row+1][col], triangle[row+1][col+1]).
2Return triangle[0][0].

Example Walkthrough

Input: [[2],[3,4],[6,5,7],[4,1,8,3]]

1.Row 2: 6+min(4,1)=7, 5+min(1,8)=6, 7+min(8,3)=10. -> [7,6,10].
2.Row 1: 3+min(7,6)=9, 4+min(6,10)=10. -> [9,10].
3.Row 0: 2+min(9,10)=11.

Output: 11

Common Pitfalls

•Process bottom-up to avoid needing an extra dp array - the triangle itself becomes the dp table.

120.cs

// Approach: Bottom-up DP starting from the second-to-last row and moving upward.
// For each cell triangle[i][j], add the minimum of triangle[i+1][j] and triangle[i+1][j+1].
// This transforms each cell into the minimum path sum from that cell to the bottom row.
// After processing all rows, triangle[0][0] contains the global minimum path sum.
// Modifying in-place avoids allocating a separate DP array, keeping extra space O(1).
// Time: O(n²) Space: O(n)

public class Solution
{
    public int MinimumTotal(IList<IList<int>> triangle)
    {
        int n = triangle.Count;
        int[][] dp = new int[n][];
        for (int i = 0; i < n; i++)
        {
            int m = triangle[i].Count;
            int[] arr = new int[m];
            Array.Fill(arr, -1);
            dp[i] = arr;
        }
        // return topDown(0, 0, triangle, dp);
        return tabulation(n, triangle, dp);
    }

    private int topDown(int r, int c, IList<IList<int>> triangle, int[][] dp)
    {
        if (r == (triangle.Count - 1))
            return triangle[r][c];

        if (dp[r][c] != -1)
            return dp[r][c];

        int down = triangle[r][c] + topDown(r + 1, c, triangle, dp);

        int cross = triangle[r][c] + topDown(r + 1, c + 1, triangle, dp);

        return dp[r][c] = Math.Min(down, cross);
    }

    private int tabulation(int r, IList<IList<int>> triangle, int[][] dp)
    {
        int[] front = new int[r];
        for (int j = 0; j < r; j++)
            front[j] = triangle[r - 1][j];

        for (int i = r - 2; i >= 0; i--)
        {
            int[] curr = new int[r];
            for (int j = i; j >= 0; j--)
            {
                int down = triangle[i][j];
                int cross = triangle[i][j];
                down += front[j];

                cross += front[j + 1];

                curr[j] = Math.Min(down, cross);
            }
            front = curr;
        }

        return front[0];
    }
}

Was this solution helpful?