You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
22 lines
455 B
22 lines
455 B
package cap4
|
|
|
|
// Ex24 树塔问题
|
|
func Ex24(nums [][]int) (int, []int) {
|
|
steps := make([]int, 0)
|
|
|
|
dp := make([][]int, len(nums))
|
|
for i, layer := range nums {
|
|
dp[i] = make([]int, len(layer))
|
|
copy(dp[i], layer)
|
|
}
|
|
|
|
for i := len(nums) - 2; i >= 0; i-- {
|
|
layer := nums[i]
|
|
for j := range layer {
|
|
// 取最大的两个来源（下层同位置和下层同位置+1）
|
|
dp[i][j] += max(dp[i+1][j], dp[i+1][j+1])
|
|
}
|
|
}
|
|
|
|
return dp[0][0], steps
|
|
}
|
|
|