Problem Statement in English

You’re given a triangle array. You have to return the minimum path sum from top to bottom.

Each step you may move to adjacent numbers on the row below. More formally, if you are on index i on the current row, you must move to either index i or index i + 1 on the next row.

Approach

This is a classic dynamic programming problem. We can use a recursive approach with memoization to solve it efficiently.

The answer for each (row, index) depends on the answers for the next row. Specifically, the minimum path sum to reach (row, index) is the value at that position plus the minimum of the path sums to reach (row + 1, index) and (row + 1, index + 1).

Solution in Python


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        
        @cache
        def dfs(i, row):
            if row >= len(triangle) or i >= len(triangle[row]):
                return 0

            v = triangle[row][i]
            row += 1
            
            return min(v + dfs(i, row), v + dfs(i + 1, row))

        return dfs(0, 0)

Complexity

  • Time: $O(n^2)$
    Since we are using memoization, each state (row, index) is computed only once. The total number of states is proportional to the number of elements in the triangle, which is $O(n^2)$ where n is the number of rows in the triangle.

  • Space: $O(n^2)$
    The space complexity is also $O(n^2)$ due to the memoization cache storing results for each state (row, index). Additionally, the recursion stack can go as deep as the number of rows in the triangle, which is O(n).

And we are done.