树形DP详解：最大独立集与监控问题

树形DP详解：最大独立集与监控问题

引用

CSDN

1.

https://blog.csdn.net/weixin_42269028/article/details/146046495

动态规划（DP）是一种非常重要的算法思想，特别是在解决树形结构问题时，树形DP更是展现出了强大的威力。本文将通过两个具体的LeetCode题目，深入讲解树形DP在最大独立集和监视相关问题中的应用。

树形DP概述

树形DP可以用于解决最大独立集和监视相关问题。这类问题通常需要在树的节点上做出选择，例如是否选择某个节点、是否在某个节点放置监视器等。树形DP通过深度优先遍历，利用动态规划的思想，根据父节点和子节点的选取状态来进行状态转移。

最大独立集问题

最大独立集是指在树中找到一个顶点集合，集合内任意两个顶点都不相邻，且顶点数量最大。树形DP非常适合解决这类问题。具体来说，可以定义两个状态：

• dp[u][0]：表示不选节点u时，以u为根的子树的最大独立集大小。此时子节点可选可不选。
• dp[u][1]：表示选节点u时，以u为根的子树的最大独立集大小。因为选了父节点，所以子节点不能选。

然后依据状态转移方程计算，最终得到整棵树的最大独立集大小。

监视相关问题

在一些监视问题中，树的每个节点代表一个区域等，需要在某些节点上放置监视器，使得所有区域都能被监视到，同时满足一定的限制条件（如监视器数量最少等）。这类问题也能转化为树形DP问题。具体来说，可以定义两个状态：

• dp[u][0]：表示节点u不放置监视器，以u为根子树都被监视到的最少监视器数量。
• dp[u][1]：表示节点u放置监视器，以u为根子树都被监视到的最少监视器数量。

再根据子节点状态推出父节点状态，从而找到全局最优解。

LeetCode 337. 打家劫舍 III

这是一道经典的树形DP题目，题目要求在不触动警报的情况下，小偷能够盗取的最高金额。具体来说，如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

题目描述

给定二叉树的root。返回在不触动警报的情况下，小偷能够盗取的最高金额。

示例

输入: root = [3,2,3,null,3,null,1]

输出: 7

解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

输入: root = [3,4,5,1,3,null,1]

输出: 9

解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示

• 树的节点数在[1, 10^4]范围内
• 0 <= Node.val <= 10^4

解题思路

对于每个节点，有两种选择：打劫或不打劫。如果打劫当前节点，那么其左右子节点都不能被打劫；如果不打劫当前节点，那么其左右子节点可以被打劫也可以不被打劫。因此，可以定义两个状态：

• rob：表示打劫当前节点时，能够获得的最大金额。
• not_rob：表示不打劫当前节点时，能够获得的最大金额。

状态转移方程如下：

• rob = l_not_rob + r_not_rob + node.val
• not_rob = max(l_rob, l_not_rob) + max(r_rob, r_not_rob)

其中，l_rob和l_not_rob分别表示左子节点被打劫和不被打劫时的最大金额，r_rob和r_not_rob分别表示右子节点被打劫和不被打劫时的最大金额。

代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        """
        时间复杂度：O(n)，其中 n 为二叉树的节点个数。
                每个节点都会递归恰好一次。
        空间复杂度：O(n)。最坏情况下，二叉树是一条链，
                递归需要 O(n) 的栈空间。
        """
        def dfs(node: Optional[TreeNode]) -> (int, int):
            if node is None:
                return 0, 0
            l_rob, l_not_rob = dfs(node.left)
            r_rob, r_not_rob = dfs(node.right)
            rob = l_not_rob + r_not_rob + node.val
            not_rob = max(l_rob, l_not_rob) + max(r_rob, r_not_rob) 
            return rob, not_rob
        
        return max(dfs(root))

LeetCode 968. 监控二叉树

这是一道关于树形DP的经典题目，题目要求计算监控树的所有节点所需的最小摄像头数量。

题目描述

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

示例

输入：[0,0,null,0,0]

输出：1

解释：如图所示，一台摄像头足以监控所有节点。

输入：[0,0,null,0,null,0,null,null,0]

输出：2

解释：需要至少两个摄像头来监视树的所有节点。上图显示了摄像头放置的有效位置之一。

提示

• 给定树的节点数的范围是[1, 1000]。
• 每个节点的值都是0。

解题思路

对于二叉树的每个节点，定义三种状态来表示节点的不同情况：

• 状态 0：表示该节点无覆盖，即该节点没有被任何监控器覆盖到。
• 状态 1：表示该节点有监控器，即该节点放置了监控器。
• 状态 2：表示该节点被覆盖，但是该节点没有监控器，是被其子节点的监控器覆盖的。

根据节点的子节点的状态来确定当前节点的状态和相应的最小监控器数量，对于每个节点node：

• 情况一：如果左子节点和右子节点至少有一个是无覆盖状态（状态 0），那么当前节点必须放置监控器，即当前节点为状态 1。因为只有当前节点放置监控器才能覆盖无覆盖的子节点，此时最小监控器数量需要加 1。
• 情况二：如果左子节点和右子节点都是被覆盖状态（状态 2），那么当前节点可以是无覆盖状态（状态 0），也可以是被覆盖状态（状态 2），但为了保证最小监控器数量，当前节点应该是无覆盖状态，由其父节点来覆盖它，此时最小监控器数量不需要增加。
• 情况三：如果左子节点或右子节点有一个是有监控器状态（状态 1），那么当前节点就是被覆盖状态（状态 2），此时最小监控器数量不需要增加。

使用深度优先搜索（DFS）来遍历二叉树，从叶子节点开始向上进行状态转移。因为叶子节点的状态比较容易确定，然后根据子节点的状态逐步确定父节点的状态，最终得到根节点的状态和整个树的最小监控器数量。

对于空节点，可以认为它是被覆盖状态（状态 2），这样可以避免在处理叶子节点时出现特殊情况。

遍历完整个二叉树后，根据根节点的状态来确定最终的最小监控器数量。如果根节点是无覆盖状态（状态 0），则需要在根节点放置一个监控器，最小监控器数量需要加 1。

代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        """
        时间复杂度：O(n)，其中 n 为二叉树的节点个数。每个节点都会递归恰好一次。
        空间复杂度：O(n)。最坏情况下，二叉树是一条链，递归需要 O(n) 的栈空间。
        """
        def dfs(node):
            if node is None:
                return inf, 0, 0  # 空节点不能安装摄像头，也无需被监控到
            l_choose, l_by_fa, l_by_children = dfs(node.left)
            r_choose, r_by_fa, r_by_children = dfs(node.right)
            choose = min(l_choose, l_by_fa) + min(r_choose, r_by_fa) + 1
            by_fa = min(l_choose, l_by_children) + min(r_choose, r_by_children)
            by_children = min(l_choose + r_by_children, l_by_children + r_choose, l_choose + r_choose)
            return choose, by_fa, by_children
        choose, _, by_children = dfs(root)  # 根节点没有父节点
        return min(choose, by_children)

通过以上树形DP的思路，可以有效地解决监控二叉树问题，找到覆盖整个二叉树所需的最少监控器数量。