Triangle

How it works

If we are allowed to modify the input triangle, we can skip creating a separate DP array entirely. We use the triangle itself to store intermediate results, applying the same bottom-up logic.

This approach uses constant extra space but modifies the input data. Each cell in the triangle gets replaced with the minimum path sum from that cell to the bottom.

Steps

1. Iterate from the second-to-last row up to the first.
2. For each cell, update triangle[row][col] += min(triangle[row+1][col], triangle[row+1][col+1]).
3. The update modifies the current cell based on the two cells directly below it.
4. After all iterations, triangle[0][0] contains the minimum path sum.
5. Return triangle[0][0].

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(1) extra space.

Things to watch for

Using Top-Down DP Without Tracking the Minimum at the Bottom

When using top-down dynamic programming, the minimum path sum ends up at one of the cells in the last row, not necessarily at a fixed position. A common mistake is to return dp[n-1][0] or dp[n-1][n-1] instead of finding the minimum across the entire bottom row. The bottom-up approach avoids this by naturally propagating the answer to dp[0][0].

Incorrect Index Handling for Adjacent Cells

In the triangle, a cell at position (row, col) can only move to (row+1, col) or (row+1, col+1). A common error is to treat this like a standard grid where you can move to col-1 as well. Since each row has exactly row+1 elements, the valid adjacent indices are strictly col and col+1 in the next row.

Forgetting to Handle Single-Element Triangles

When the triangle has only one row with a single element, some implementations may fail if they assume there are at least two rows. Always ensure your base case or loop bounds correctly handle the edge case where n == 1, returning the single element as the answer.

from typing import List

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for row in range(len(triangle) - 2, -1, -1):
            for col in range(len(triangle[row])):
                triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1])

        return triangle[0][0]

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