【算法日记】Day 15 动态规划专题——树状DP基础（三）

Abstract：#动态规划#树状DP#贪心策略

1. 题目

• 题目：LeetCode 968. 监控二叉树
• 核心思路：每个摄像头可以覆盖自身、父节点和直接子节点。为了最小化摄像头数量，采用贪心策略，自底向上遍历。每个节点有3种状态：0（无覆盖）、1（有覆盖无摄像头）、2（有覆盖有摄像头）。空节点统一返回状态1。对于非空节点，如果其任一子节点处于无覆盖，则该节点必须放置摄像头；如果任一子节点有摄像头，则该节点被覆盖，按照贪心策略无需再放置摄像头；否则，左右子节点均为有覆盖无摄像头状态，该节点处于无覆盖状态0。按照策略将状态逐层向上传递。
• 复杂度：时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( h e i g h t ) O(height)O(height)。

2. 代码

classSolution{public:intans;intstate(TreeNode*x){if(x==nullptr)return1;intleft=state(x->left);intright=state(x->right);if(left==0||right==0){ans++;return2;}if(left==1&&right==1)return0;return1;}intminCameraCover(TreeNode*root){ans=0;intfinalState=state(root);if(finalState==0)ans++;returnans;}};

3. 心得

• 复盘思路：这道题目的转移情况我独立想出来了（尽管没有意识到是贪心的思想），但是在实现方式上却禁锢在之前树状DP问题的状态传递方式了。更精确地说，我被局限在“放与不放”这个二元的状态中，但此题因为摄像头覆盖规则复杂，仅靠二元状态无法表达节点被谁覆盖的情况（父节点、子节点还是自身），必须区分“有覆盖无摄像头”和“有覆盖有摄像头”，因此加上“无覆盖”需要3个状态。既然已经从状态入手了，结合贪心的策略（只有存在无覆盖子结点的时候才要放置，答案才需要加一）可以知道，我们需要传递的只是状态，根据状态我们就可以判断是否在总答案中加一。
• Special Case：
  1. 空结点：不需要被监控，视为“有覆盖无摄像头”。这样叶子节点的左右子节点状态均为1，叶子节点自身状态就为0，触发父节点放置摄像头。
  2. 如果若根节点返回状态0，证明根节点还未被其子结点覆盖，需在根节点额外放置一个摄像头。

4. 相关题目

• Luogu P2458 保安站岗