# 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
}
}
``````

Nothing just happens, it's all part of a plan.