树形dp 打家劫舍Ⅲ+监控二叉树

树形dp，递归调用栈把中间计算结果暂存了，子调用的结果交给父调用，它就销毁了，不需要记忆化。

解题时确定每个节点的所有状态，并从子调用逐个返回。

打家劫舍Ⅲ

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
struct Node {
    Node(){}
    Node(int rob, int norob):rob(rob),norob(norob){}
    int rob, norob;
};
class Solution {
public:
    Node dfs(TreeNode* rt) {
        if(rt == nullptr) {
            return Node(0, 0);
        }

        auto l = dfs(rt -> left);
        auto r = dfs(rt -> right);

        int rob = rt -> val + l.norob + r.norob;
        int norob = max(l.rob+r.rob, max(l.rob+r.norob, max(l.norob+r.rob, l.norob+r.norob)));

        return Node(rob, norob);
    }
    int rob(TreeNode* root) {
        auto res = dfs(root);
        return max(res.rob, res.norob);
    }
};
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
32
33
34
35
36

监控二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    struct Node {
        Node(){}
        Node(int withCam, int noCamWithFa, int noCamWithSon):withCam(withCam), noCamWithFa(noCamWithFa), noCamWithSon(noCamWithSon){}
        int withCam, noCamWithFa, noCamWithSon;
    };
    Node dfs(TreeNode* rt) {
        if(rt == nullptr) {
            return Node(0x3f3f3f, 0, 0);
        }

        Node l = dfs(rt -> left);
        Node r = dfs(rt -> right);
		
		// 确定不是最优的状态也不需要完全枚举
        int withCam = 1+min(l.withCam+r.withCam, 
        min(l.noCamWithFa+r.noCamWithFa, 
        min(l.withCam+r.noCamWithFa,
        l.noCamWithFa+r.withCam)));

        int noCamWithFa = min(l.noCamWithSon+r.noCamWithSon,
        min(l.withCam+r.noCamWithSon,
        min(l.withCam+r.withCam,
        r.withCam+l.noCamWithSon)
        ));

        int noCamWithSon = min(l.withCam+r.withCam,
        min(l.withCam+r.noCamWithSon, r.withCam+l.noCamWithSon)
        );

        return Node(withCam, noCamWithFa, noCamWithSon);
    }

    int minCameraCover(TreeNode* root) {
        auto res = dfs(root);
        return min(res.withCam, res.noCamWithSon);
    }
};
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50