什么是树形DP
顾名思义,树形DP就是在某些题目中要求的树结构上使用DP的思想。
树是有n个节点,n-1条边的无向图,且是无环的,联通的,又因为是无向图,所以两个节点间存在着相互的联通关系,有时需要加以判断
当DP建立在依赖关系上时,就可以使用树形DP来解决问题。
树形DP模板
void dfs(u,fa,other): //u为当前节点,fa为其父节点,other为其他参数
if special
do sth
for each v (存在 u->v)
if v=fa continue //因为会与父亲也存在联通关系,所以特判
dfs(v,u) //因为需要依靠子树的结果来推导自身,所以先继续深入子树
do dp //进行dp运算
树形DP题目
P1352 没有上司的舞会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
根据网友们所说,这是一道树形DP的经典题目,通过它可以初见端倪,做完后确实如此。
通过分析题意,很容易将树构建出来。当树构建完毕后,不难想到,一个上司的状态会影响其手下所有员工的状态(当上司来时,其子树所有节点均不能来;当上司不来时,其子树所有节点可以来,也可以不来,对应两种状态,我们这时可以取两种状态的最大值,保证最优)
有了以上分析,我们就可以尝试推敲状态转移方程,如下:
首先分析第一个状态,即当前节点(在编写dp函数时,关注于树上单个节点,也就是最小子问题,切勿写着写着迷糊的过早思考全局)来参加舞会的状态。如果当前节点来参加舞会,那么其子树中所有节点都不能来参加,于是自然地得出以下公式:
我们用一个二维数组来保存每个节点的dp结果,此处有一个小技巧,我们可以将大小较小的那一维度尽可能放在前面,使得计算机可以更快的运行代码。规定0为不参会,1为参会,children为当前节点的子节点数组,value为树中节点权值数组。
然后同样分析得出当前节点参会的状态:
至此,全部的两个状态就分析完毕了。在计算dp结果的过程中,可能会遇到已经计算过的节点,例如两个不同节点的邻居(在一条链上的中点)相当于会重复遇到,所以我们再额外创建一个bool类型的数组来判断即可。
代码如下:
package main
import "fmt"
//洛谷的Go版本低于1.18,用不了泛型……
//func max[T int](nums ...T) T {
// var max T
// max = nums[0]
// for _, v := range nums {
// if max < v {
// max = v
// }
// }
// return max
//}
func max(nums ...int) int {
var max int
max = nums[0]
for _, v := range nums {
if max < v {
max = v
}
}
return max
}
func main() {
var treeSize int
var input int
_, err := fmt.Scanf("%d", &treeSize)
if err != nil {
fmt.Print("Input error")
}
dpTable := make([][]int, 2)
for i := range dpTable {
dpTable[i] = make([]int, treeSize+1)
}
hasFather := make([]bool, treeSize+1)
isVisited := make([]bool, treeSize+1)
happyNumber := make([]int, treeSize+1)
tree := make([][]int, treeSize+1)
rootNode := 0
for i := 0; i <= treeSize; i++ {
fmt.Scanln(&input)
happyNumber[i] = input
}
for i := 0; i < treeSize-1; i++ {
var employee, employer int
fmt.Scanln(&employee, &employer)
hasFather[employee] = true
tree[employer] = append(tree[employer], employee)
}
var treeDP func(node int)
treeDP = func(node int) {
isVisited[node] = true
dpTable[1][node] = happyNumber[node]
for _, v := range tree[node] {
if isVisited[v] {
continue
}
treeDP(v)
dpTable[0][node] += max(dpTable[0][v], dpTable[1][v])
dpTable[1][node] += dpTable[0][v]
}
}
for i := 1; i < len(hasFather); i++ {
if !hasFather[i] {
rootNode = i
break
}
}
treeDP(rootNode)
fmt.Print(max(dpTable[0][rootNode], dpTable[1][rootNode]))
}
337. 打家劫舍 III - 力扣(LeetCode)
这个题目和舞会题目基本相同,甚至感觉还更简单一些……
还是相同的思考方式,读题后不难想到,一个房子有两个状态,即偷这个房子和不偷这个房子,那么接下来就是对这两种状态进行状态转移方程的书写:
同样是二维数组,其中0表示偷当前节点,1表示不偷当前节点,很好理解上面的式子
\[f[1][i] = max(f[0][left],f[1][left])+max(f[0][right],f[1][right]) \]偷当前节点时,左右子节点可以偷也可以不偷,所以我们取其中的最大值为抉择方案
最后就是结束条件,显而易见,当达到空节点时就返回,那么空节点是没法被偷的,无论是偷还是不偷,拿到的价值都是0,而且对结果也不会产生影响,所以我们遇到空节点时就返回两个0对应两个状态即可。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
var dpTree func(root *TreeNode) (int, int)
dpTree = func(root *TreeNode) (int, int) {
if root == nil {
return 0, 0
}
left_withoutRob, left_rob := dpTree(root.Left)
right_withoutRob, right_rob := dpTree(root.Right)
root_withoutRob := max[int](left_rob, left_withoutRob) + max[int](right_rob, right_withoutRob)
root_rob := left_withoutRob + right_withoutRob + root.Val
return root_withoutRob, root_rob
}
return max[int](dpTree(root))
}
func max[T int](nums ...T) T {
var max T
max = nums[0]
for _, v := range nums {
if max < v {
max = v
}
}
return max
}