步骤一：定义子问题
步骤二：写出子问题的递推关系
步骤三：确定 DP 数组的计算顺序
步骤四：空间优化
滚动数组思想
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
p, q, r := 1, 1, 2
for i:=3; i<=n; i++ {
p = q
q = r
r = p + q
}
return r
}
func rob(nums []int) int {
// DP(x) = MAX(DP(x-1), DP(x-2) + f(x))
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
return nums[0]
}
if len(nums) == 2 {
if nums[0] > nums[1] {
return nums[0]
}
return nums[1]
}
a, b, res := 0, 0, 0
for i, num := range(nums) {
if i == 0 {
a = num
continue
}
if i == 1 {
if a > num {
b = a
} else {
b = num
}
continue
}
if b > a+num {
res = b
} else {
res = a+num
}
a = b
b = res
}
return res
}
- 需要先找到每个节点对应的
最大贡献值 Score，然后再找最终答案。 - 但是不必递归两次，仅需在一次递归中完成最大贡献值的查找以及最终答案的更新，性情见标准答案。
- 可以使用
math.MinInt32。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type TreeNodeNew struct {
Val int
Score int
Left *TreeNodeNew
Right *TreeNodeNew
}
func (t *TreeNodeNew) GetVal() int {
if t == nil {
return 0
}
return t.Val
}
func (t *TreeNodeNew) GetScore() int {
if t == nil {
return 0
}
return t.Score
}
var res int
func maxPathSum(root *TreeNode) int {
res = -65535
rootNew := New(root)
sum(rootNew)
fmt.Printf("%v", rootNew)
return res
}
func sum(root *TreeNodeNew) {
if root == nil {
return
}
res = max(res, root.GetVal() + root.Left.GetScore() + root.Right.GetScore())
sum(root.Left)
sum(root.Right)
}
func New(root *TreeNode) *TreeNodeNew {
if root == nil {
return nil
}
left := New(root.Left)
right := New(root.Right)
var score int
if left.GetScore() < 0 && right.GetScore() < 0 {
score = max(root.Val, 0)
} else if left.GetScore() < 0 {
score = max(root.Val + right.GetScore(), 0)
} else if right.GetScore() < 0 {
score = max(root.Val + left.GetScore(), 0)
} else {
score = max(root.Val + max(left.GetScore(), right.GetScore()), 0)
}
return &TreeNodeNew{
Val: root.Val,
Score: score,
Left: left,
Right: right,
}
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}
func val(root *TreeNode) int {
if root == nil {
return 0
}
return root.Val
}
标准答案：
func maxPathSum(root *TreeNode) int {
maxSum := math.MinInt32
var maxGain func(*TreeNode) int
maxGain = func(node *TreeNode) int {
if node == nil {
return 0
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时，才会选取对应子节点
leftGain := max(maxGain(node.Left), 0)
rightGain := max(maxGain(node.Right), 0)
// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
priceNewPath := node.Val + leftGain + rightGain
// 更新答案
maxSum = max(maxSum, priceNewPath)
// 返回节点的最大贡献值
return node.Val + max(leftGain, rightGain)
}
maxGain(root)
return maxSum
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
func myPow(x float64, n int) float64 {
var res float64
res = 1.0
if n == 0 {
return res
}
if n > 0 {
if n % 2 == 0 {
return pow2(myPow(x, n/2))
} else {
return pow2(myPow(x, (n-1)/2)) * x
}
} else {
if n % 2 == 0 {
return pow2(myPow(x, n/2))
} else {
return pow2(myPow(x, (n+1)/2)) / x
}
}
return res
}
func pow2(x float64) float64 {
return x*x
}
// func myPow(x float64, n int) float64 {
// var res float64
// res = 1.0
// if n >= 0 {
// for i := 0 ; i < n ; i++ {
// res = res * x
// }
// } else {
// for i := 0 ; i > n ; i-- {
// res = res / x
// }
// }
// return res
// }
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 nz_nuaa@163.com