Triangle — LeetCode 120 Python Solution

The problem

Given a triangle array, return the minimum path sum from top to bottom. For each step, you may move to an adjacent number of the row below.

Example

Input

triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

Output

11

Explanation

The triangle looks like:

Python solution

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

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 120. Triangle is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems