首页 > 其他分享 >树形DP

树形DP

时间:2023-09-23 19:44:30浏览次数:37  
标签:nums int max 树形 root 节点 DP

什么是树形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函数时,关注于树上单个节点,也就是最小子问题,切勿写着写着迷糊的过早思考全局)来参加舞会的状态。如果当前节点来参加舞会,那么其子树中所有节点都不能来参加,于是自然地得出以下公式:

\[f[1][i] = \sum_{0}^{children.size} f[0][v] + value[i] \]

我们用一个二维数组来保存每个节点的dp结果,此处有一个小技巧,我们可以将大小较小的那一维度尽可能放在前面,使得计算机可以更快的运行代码。规定0为不参会,1为参会,children为当前节点的子节点数组,value为树中节点权值数组。
然后同样分析得出当前节点参会的状态:

\[f[0][i] = \sum_{0}^{children.size} max(f[0][v],f[1][v]) \]

至此,全部的两个状态就分析完毕了。在计算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)

这个题目和舞会题目基本相同,甚至感觉还更简单一些……
还是相同的思考方式,读题后不难想到,一个房子有两个状态,即偷这个房子和不偷这个房子,那么接下来就是对这两种状态进行状态转移方程的书写:

\[f[0][i] = f[1][left]+f[1][right]+root.val \]

同样是二维数组,其中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

}

未完待续

标签:nums,int,max,树形,root,节点,DP
From: https://www.cnblogs.com/appletree24/p/17724960.html

相关文章

  • ThreadPoolExecutor线程池
    ......
  • 最大子树和(树形dp)
    题意题目链接:https://www.luogu.com.cn/problem/P1122给一棵树,树上的每个节点都有一个值,然后你可以剪掉一些节点,问最后你能得到的最大的和。(因为有些节点的值为负数。)思路典型树形dp。跑一遍dfs就行。从1开始搜,f[i]代表以i为根节点往下能得到的最大值,然后我们从......
  • 落基山脉(区间dp)
    题意题目链接:https://www.luogu.com.cn/problem/P9325给一段山脉的高度,然后从中截取一段长度为i的区间,求最小不对称值。不对称值就是这段区间里,最左边的高度与最右边的高度的差值加上倒数第二和第二,……。然后输出区间长度从1到n的最小不对称值。思路很容易想到......
  • P7916 [CSP-S 2021] 交通规划 sol-最短路+环形dp
    P7916[CSP-S2021]交通规划solStatement传送门Solution好题。发现\(k\le2\)的分值非常多,于是我们考虑从\(k=2\)入手。颜色相同就不用说了,直接染成同一种颜色就行了。我们考虑其他情况,就是颜色不相同的情况,我们一定是找了一条路径把这个图给切开了就像这个样子。......
  • 学不会的动态规划——状压DP
    前言不知道为什么越是接近网络赛就越是静不下心来,可能也是因为开学了吧,QAQ,有一说一还是暑假比较适合训练。第一场网络赛,特意选了一个属于我们队的“风水宝地”(其实是我们去的早获得了优先选择权),但是好像并没有什么用,读题读巨慢,还被签到卡了2h(大概,有点不记得了),最后开j,队友推公式写......
  • Exam DP-300: Administering Microsoft Azure SQL Solutions 微软Azure SQL Solutions
    作为该考试的考生,您应具备构建数据库解决方案方面的主题专业知识,这些解决方案旨在支持使用数据库构建的多种工作负载:企业内部SQLServerAzureSQL服务您是一名数据库管理员,负责管理使用SQLServer和AzureSQL服务构建的内部部署和云数据库。作为Azure数据库管理员,您......
  • 小白也能看懂的插件化DroidPlugin原理(三)-- 如何拦截startActivity方法
    **前言:**在前两篇文章中分别介绍了动态代理、反射机制和Hook机制,如果对这些还不太了解的童鞋建议先去参考一下前两篇文章。经过了前面两篇文章的铺垫,终于可以玩点真刀实弹的了,本篇将会通过Hook掉startActivity方法的一个小例子来介绍如何找出合适的Hook切入点。开始之前我们......
  • # github.com/coreos/etcd/clientv3/balancer/resolver/endpoint
    linux使用go连接etcd集群时报错:#github.com/coreos/etcd/clientv3/balancer/resolver/endpoint/root/go/pkg/mod/github.com/coreos/[email protected]+incompatible/clientv3/balancer/resolver/endpoint/endpoint.go:114:87:undefined:resolver.BuildOption/root/go/pkg/mod/g......
  • kubernetes初始化时报错:CRI v1 runtime API is not implemented for endpoint \"unix
    近日,进行Kubernetes初始化时报错如下:[root@k8s-master~]#kubeadminit--kubernetes-version=v1.28.2--pod-network-cidr=10.244.0.0/16--service-cidr=10.96.0.0/12--apiserver-advertise-address=10.10.10.185[init]UsingKubernetesversion:v1.28.2[preflight]Runn......
  • PHP多层级菜单树形结构递归处理
    如题:一、数据库菜单数据表使用图片中id和parent_id两个参数来关联父子关系二、将数据库中的数据变成树状多层级解构```{ "id":1, "parentId":0, "treePath":"0", "name":"系统管理", "type":2, "path":"/system",......