> For the complete documentation index, see [llms.txt](https://leetcodebook-1.gitbook.io/top-interview-150/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcodebook-1.gitbook.io/top-interview-150/dynamic/triangle.md).

# 三角形最小路径和

题目链接: <https://leetcode.cn/problems/triangle/>

## 解题思路：

1. 设定dp\[i]\[j],代表自顶至下到\[i]\[j]位置最小路径和
2. 二维数组为三角形,结合题干和提示可知,j<=i
3. dp\[0]\[0]=triangle\[0]\[0]
4. dp\[i]\[j]=min(dp\[i-1]\[j-1]+triangle\[i]\[j],dp\[i]\[j-1]+triangle\[i]\[j])
5. dp\[i]\[0]和dp\[i]\[i]的位置需要特殊处理
6. 最终遍历dp\[n-1]\[i]获取路径最小值

```go
func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    if n == 0 {
        return 0
    }
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, i+1)
    }
    dp[0][0] = triangle[0][0]
    for i := 1; i < n; i++ {
        dp[i][0] = dp[i-1][0] + triangle[i][0]
        for j := 1; j < i; j++ {
            dp[i][j] = min(dp[i-1][j-1]+triangle[i][j], dp[i-1][j]+triangle[i][j])
        }
        dp[i][i] = dp[i-1][i-1] + triangle[i][i]
    }
    Min := 10001
    for i:=0;i<n;i++{
        Min =min(Min,dp[n-1][i])
    }
    return Min
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

## 复杂度分析

* **时间复杂度：** 时间复杂度是 $$O(n^2)$$，其中 $$n$$ 是数组 `triangle` 的长度
* **空间复杂度：** 空间复杂度是 $$O(n^2)$$，我们需要一个边长为n的等腰直角三角形大小的二维数组。