> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/1-200/120.-san-jiao-xing-zui-xiao-lu-jing-he.md).

# 120. 三角形最小路径和

<https://leetcode-cn.com/problems/triangle/>

## 解法一：dp

用一个一维dp数组，自底向上迭代即可。dp初始为三角形倒数第一行，从倒数第二行开始迭代。`dp[j]`的新值为相邻位置较小值加上当前位置三角形的值

```python
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = triangle[-1]
        for i in range(len(triangle)-2, -1, -1):    #自底向上，对三角形的每行
            for j in range(len(triangle[i])):    #从左到右，对三角形该行的每个位置
                dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
        return dp[0]
```