# \[120]\[中等]\[动态规划] 三角形最小路径和

## 题目描述

[120. 三角形最小路径和](https://leetcode-cn.com/problems/triangle/)

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

```
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
```

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

## 解题思路

### 动态规划

第$$i$$行第$$j$$个数字与上一行的$$(i-1, j-1)$$和$$(i-1, j)$$两个数字相邻, 因此到达此点的最小路径等于它的**两个相邻结点中最小路径中的较小者**加上这一点的值, 对应的状态转移方程得出.

这样需要创建一个$$n \times n$$大小的矩阵来存储状态, 但求$$i$$行中点的最小路径只用到$$i-1$$的值, 因此使用滚动数组, 需要的空间复杂度为$$O(n)$$.

```python
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        last = [1e12] * n
        last[0] = triangle[0][0]

        for i in range(1, n):
            new_dp = [0] * n
            for j in range(i + 1):
                new_dp[j] = min(last[j - 1] if j - 1 >= 0 else 1e12, last[j] if j < i else 1e12) + triangle[i][j]
            last = new_dp
        return min(last)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/120-san-jiao-xing-zui-xiao-lu-jing-he.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.