#120

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Triangle

Given a triangle, return the minimum path sum from top to bottom, moving to adjacent numbers in the row below.

Problem Statement

You are given a triangle represented as a 2D array. The task is to find the minimum path sum from top to bottom. At each step, you can move to an adjacent number in the row directly below.

More specifically, if you're currently at index i in the row, you can move either to index i or index i+1 in the next row. Your goal is to return the minimum sum of the path that starts from the top and ends at the bottom.

Examples

Example 1

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

Output: 11

The triangle looks like: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2

Input: triangle = [[-10]]

Output: -10

Example details omitted.

Constraints

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104

Solution Approach

Bottom-Up Dynamic Programming

Start from the second-to-last row and move upwards, updating each element with the minimum sum path from that element to the bottom. This modifies the triangle in place, reducing space complexity.

State Transition Optimization

By focusing on state transitions, we can optimize the solution by updating only two rows at a time. This reduces both space and time complexity, as we no longer need to store the entire triangle.

Iterative Bottom-Up Approach

An alternative bottom-up approach involves using an array to store the minimum sums from the bottom of the triangle. This avoids altering the triangle itself, maintaining original input integrity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n) because we process each element once, where n is the total number of elements in the triangle. The space complexity is O(n) for the iterative approach using an auxiliary array, or O(1) if modifying the triangle in place.

What Interviewers Usually Probe

The candidate demonstrates strong understanding of dynamic programming by recognizing the optimal bottom-up approach.
The candidate effectively reduces space complexity by updating the triangle in place or using a two-row technique.
The candidate struggles with the pattern of state transition optimization or proposes inefficient solutions.

Common Pitfalls or Variants

Common pitfalls

Over-complicating the problem by using a top-down approach, which leads to redundant calculations and higher time complexity.
Not correctly handling edge cases, such as when the triangle has only one element.
Confusing the minimum sum path with a simple greedy approach, which may not yield the correct result.

Follow-up variants

Modify the problem to allow only movements to the left or right, rather than adjacent numbers.
Extend the problem to find the maximum path sum instead of the minimum.
Solve the problem with a variant where the triangle elements are non-integer values, such as decimals or negative numbers.

FAQ

How do I approach the Triangle problem with dynamic programming?

Start from the bottom of the triangle and update each element by adding the minimum path sum from the row directly below. This is the key to the bottom-up approach.

Can I use a top-down approach for the Triangle problem?

While a top-down approach works, it is less efficient because it involves redundant calculations. The bottom-up approach is recommended for better performance.

What is the optimal space complexity for the Triangle problem?

The optimal space complexity is O(1) if you modify the triangle in place or O(n) if you use an auxiliary array to store intermediate results.

What is the time complexity of solving the Triangle problem using dynamic programming?

The time complexity is O(n), where n is the total number of elements in the triangle, because each element is processed only once.

What are some common mistakes when solving the Triangle problem?

Common mistakes include over-complicating the solution with a top-down approach, incorrectly handling edge cases, and confusing greedy strategies with dynamic programming.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the minimum path sum from the bottom of the triangle to position $(i, j)$. Here, position $(i, j)$ refers to the position in row $i$ and column $j$ of the triangle (both indexed from $0$). We have the following state transition equation:

1

2

3

4

5

6

7

8

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]

Solution 2: Dynamic Programming (Space Optimization)

We notice that the state $f[i][j]$ only depends on states $f[i + 1][j]$ and $f[i + 1][j + 1]$. Therefore, we can use a one-dimensional array instead of a two-dimensional array, reducing the space complexity from $O(n^2)$ to $O(n)$.

1

2

3

4

5

6

7

8

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]

Continue Practicing

#119 pascals triangle ii #121 best time to buy and sell stock #118 pascals triangle