Problem #120: Triangle

Intuition & Strategy Breakdown

Use dynamic programming from bottom to top. dp[j] = triangle[i][j] + min(dp[j], dp[j+1]), reducing required space to a single array.

Python Solution

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

Java Solution

class Solution {
    public int minimumTotal(List> triangle) {
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                int below = Math.min(
                    triangle.get(i + 1).get(j),
                    triangle.get(i + 1).get(j + 1)
                );
                triangle.get(i).set(j, triangle.get(i).get(j) + below);
            }
        }
        return triangle.get(0).get(0);
    }
}