# Dynamic Programming - 120. Triangle

120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

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

The minimum path sum from top to bottom is `11` (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

go：

```/*func minimumTotal(triangle [][]int) int {

if triangle == nil || len(triangle) == 0 {
return 0
}

m := len(triangle)
dp := make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, len(triangle[i]))
}

for i := m - 1; i >= 0; i-- {
for j := 0; j < len(triangle[i]); j++ {
if i == m-1 {
dp[i][j] = triangle[i][j]
} else {
dp[i][j] = min(dp[i+1][j] + triangle[i][j], dp[i+1][j+1] + triangle[i][j])
}
}
}

return dp[0][0]
}*/

func minimumTotal(triangle [][]int) int {
if triangle == nil || len(triangle) == 0 {
return 0
}

m := len(triangle)
dp := make([]int, m)

for i := m - 1; i >= 0; i-- {
for j := 0; j < len(triangle[i]); j++ {
if i == m-1 {
dp[j] = triangle[i][j]
} else {
dp[j] = min(dp[j] + triangle[i][j], dp[j+1] + triangle[i][j])
}
}
}
return dp[0]
}

func min(i, j int) int {
if i < j {
return i
} else {
return j
}
}```

0 条评论

• ### Dynamic Programming - 375. Guess Number Higher or Lower II

We are playing the Guess Game. The game is as follows:

• ### Dynamic Programming - 279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for...

• ### Tree - 124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

• ### Leetcode Golang 120. Triangle.go

版权声明：原创勿转 https://blog.csdn.net/anakinsun/article/details/88965777

• ### LeetCode 120 Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you ma...

• ### 【leetcode刷题】T160-三角形最小路径和

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

• ### 三角形最小路径和

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

• ### 一天一大 leet(三角形最小路径和)难度:中等-Day20200714

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

• ### Golang Leetcode 202. Happy Number.go

版权声明：原创勿转 https://blog.csdn.net/anakinsun/article/details/89012332

• ### C程序设计(第四版)课后习题完整版 谭浩强编著

答：程序就是一组计算机能识别和执行的指令。 程序设计是指从确定任务到得到结果，写出文档的全过程。(一般经历6个阶段:①问题分析;②设计算法;③编写程序;④对源程...