算法leetcode

【树形DP】力扣968-监控二叉树

字数统计: 1.4k字   |   阅读时长: 5分
, ,

摘要: 力扣 968, 状态比较复杂的树形 DP 题目

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，在文章 【树形DP】树的直径 中，我们学习了树形 DP 的经典题目：树的直径，理解了树形 DP 的基本思想。

本文我们看一个状态稍微复杂一点的树形 DP。在本题中，计算当前节点 u 的状态的时候，首先递归地计算各个子节点的状态并返回，根据返回的子节点的状态来计算当前节点 u 的状态。这些子节点的状态在完成当前节点的状态计算之后就不会再用了，因此这类树形 DP 实现的时候就按照树的后序遍历来就行，只是需要额外传递一些参数。下面我们看题目。

题目

968. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

提示：

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

示例 1：
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

示例 2：
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

题解

算法: 树形DP

我们整棵树的每个节点都要考虑是否将该节点选为安装摄像头的节点。

考虑后序遍历的过程，对于遍历到的每个节点为 u，我们求一下监控到 u 这棵子树的每个节点最少需要的摄像头个数 dp[u]，则 dp[root] 就是我们要求的监控整棵树所需的最少摄像头个数。

按照通常的思路，我们可以把当前节点分为选和不选两种情况，分别计算这两种情况下的最少摄像头个数。具体就是 dp[u][0] 为选择 u 的情况下监控 u 子树的最少摄像头个数；dp[u][1] 为不选择 u 的情况下监控 u 子树的最少摄像头个数。然后 min(dp[u][0], dp[u][1]) 即为监控 u 子树所需的最少摄像头个数。

但是除了 dp[u][0], dp[u][1] 之外，还有一种状态我们是需要知道的，也就是当不选择 u 的时候，并且 u 的各个子节点也都没有选，那么此时 u 实际上并没有覆盖到。虽然 u 的各个子节点都没有选，但是这些子节点却有可能被它们的子节点，也就是 u 的孙子节点监控到，这样就形成了 u 子树上除了 u 节点本身没有监控到，其余节点都被监控到的情况。这种情况也是有可能的，也就是 u 如果有父节点且父节点选了的话，那么 u 节点实际上还是被监控到的。

因此我们需要额外的一个状态 dp[u][2] 记录不选 u，且 u 也没有被 u 的子节点监控到的情况下，u 子树所需的最少摄像头个数。

综合以上分析，我们的树形 DP 的状态设计和状态转移如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
状态定义:
dp[u][0] := 选 u 的情况下，监控 u 子树所需的最少摄像头个数
dp[u][1] := 不选 u 的情况下，监控 u 子树所需的最少摄像头个数
dp[u][2] := 不选 u 的情况下，监控 u 子树上除了 u 节点以外的所有节点所需的最少摄像头个数

答案:
result = min(dp[root][0], dp[root][1])

初始化:
dp[null][0] = INT_MAX / 2
dp[null][1] = 0
dp[null][2] = 0

状态转移:
dp[u][0] = min(dp[left][0], dp[left][1], dp[left][2])
           + min(dp[right][0], dp[right][1], dp[right][2])
           + 1
dp[u][1] = min(dp[left][0] + min(dp[right][0], dp[right][1])
              ,dp[right][0] + min(dp[left][0], dp[left][1]))
dp[u][2] = dp[left][1] + dp[right][1]

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int minCameraCover(TreeNode* root) {
        if(!root) 
            return 0;
        vector<int> dp = _postOrder(root);
        return min(dp[0], dp[1]);
    }

private:
    vector<int> _postOrder(TreeNode* node)
    {
        if(!node)
            return {INT_MAX / 2, 0, 0};

        vector<int> dp(3, 0);
        vector<int> dp_left(3, 0);
        vector<int> dp_right(3, 0);

        dp_left = _postOrder(node -> left);
        dp_right = _postOrder(node -> right);

        dp[0] = min(min(dp_left[0], dp_left[1]), dp_left[2])
                + min(min(dp_right[0], dp_right[1]), dp_right[2])
                + 1;
        dp[1] = min(dp_left[0] + min(dp_right[0], dp_right[1])
                   ,dp_right[0] + min(dp_left[0], dp_left[1]));
        dp[2] = dp_left[1] + dp_right[1];
        return dp;
    }
};

总结

可以看到，本题与 【树形DP】树的直径 相比，状态上更加复杂，如果用后序遍历来完成各个节点的状态的计算的话，每个节点完成计算后需要返回 3 个值供父节点计算使用。

有了本题的基础之后，下一篇文章我们来研究秋季赛的第 4 题 — 二叉树灯饰。

Share