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.

#120

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 …

数组动态规划

题目描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

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

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示从三角形底部走到位置 $(i, j)$ 的最小路径和。这里的位置 $(i, j)$ 指的是三角形中第 $i$ 行第 $j$ 列（均从 $0$ 开始编号）的位置。那么我们有如下的状态转移方程：

f[i][j] = \min(f[i + 1][j], f[i + 1][j + 1]) + \text{triangle}[i][j]

答案即为 $f[0][0]$ 。

1

2

3

4

5

6

7

8

9

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]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#119 杨辉三角 II #121 买卖股票的最佳时机 #118 杨辉三角