题目
给定一个三角形，找出自顶向下的最小路径和.每一步只能移动到下一行中相邻的结点上.
思路
把三角形转换成靠左对齐的一个个子块理解
那么到第 i 层的第 j 个子块的最短路径和等于:
第 i-1 层第 j-1 个子块加第 i 层的第 j 个子块
第 i-1 层第 j 个子块加第 i 层的第 j 个子块
这两者的最小值
状态转移方程
dp[i][j] = min(dp[i-1][j-1]+dp[i-1][j])+triangle[i][j]
最终代码
func calc(triangle [][]int) int {
length := len(triangle)
if length < 1 {
return 0
}
if length == 1 {
return triangle[0][0]
}
dp := make([][]int, length)
for i, each := range triangle {
dp[i] = make([]int, len(each))
}
result := math.MaxInt32
dp[0][0] = triangle[0][0]
dp[1][1] = triangle[1][1] + triangle[0][0]
dp[1][0] = triangle[1][0] + triangle[0][0]
for i := 2; i < length; i++ {
for j := 0; j < len(triangle[i]); j++ {
if j == 0 {
dp[i][j] = dp[i-1][j] + triangle[i][j]
} else if j == (len(triangle[i]) - 1) {
dp[i][j] = dp[i-1][j-1] + triangle[i][j]
} else {
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
}
}
}
for _, k := range dp[length-1] {
result = min(result, k)
}
return result
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
