算法疑难杂症

2022力扣秋季赛第4题

字数统计: 3.5k字   |   阅读时长: 15分
,

摘要: 2022 力扣秋季赛第 4 题，状态复杂到搞人心态的二叉树上的树形 DP 题目

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

本文我们来研究一下力扣秋季赛第 4 题，也就是 LCP64，本题是一个在二叉树上以后序遍历的方式实现树形 DP 但是状态比较复杂的问题。比赛的时候看出了是树形 DP 但是没有分析清楚状态，比较可惜。

在前两篇文章 【树形DP】树的直径、【树形DP】力扣968-监控二叉树 中，我们以树的直径这个经典问题了解了树形 DP 的原理和实现，然后了解了二叉树上以后序遍历的方式实现状态比较复杂的树形 DP 的做法。

本题在思路上类似，也是先通过分析找到在所需的状态，然后进行定义，梳理清楚状态的转移方式，最后以后序遍历的方式实现。说起来还是很容易的，但是实际做的时候就搞人心态了，本题的状态设计需要分析很多种情况，状态设计出来之后，状态转移又有很多种转移方式，需要一条一条写出来，光是体力活就有很多。看到后面就知道了。

题目

LCP 64. 二叉树灯饰

一个二叉树形状的装饰树。每个节点上均有一盏灯和三个开关。节点值为 0 表示灯处于「关闭」状态，节点值为 1 表示灯处于「开启」状态。每个节点上的三个开关各自功能如下：

开关 1：切换当前节点的灯的状态；
开关 2：切换 以当前节点为根 的子树中，所有节点上的灯的状态，；
开关 3：切换 当前节点及其左右子节点（若存在的话） 上的灯的状态；

给定该装饰的初始状态 root，请返回最少需要操作多少次开关，可以关闭所有节点的灯。

提示：

1
2
1 <= 节点个数 <= 10^5
0 <= Node.val <= 1

样例:

示例 1：
输入：root = [1,1,0,null,null,null,1]
输出：2
示例 2：
输入：root = [1,1,1,1,null,null,1]
输出：1
示例 3：
输入：root = [0,null,0]
输出：0

题解

算法1: 树形DP, 以子树返回的额外信息设计状态

考虑后序遍历的过程，对于遍历到的每个节点为 u，我们求一下将 u 这棵子树的每个节点都熄灭所需的最少按开关次数 dp[u]，则 dp[root] 就是我们要求的将整棵树都熄灭所需的最少按开关次数。

由于每个节点有三种开关，因此当考虑一个节点时，共有 8 种选择：

1
2
3
4
5
6
7
8
按法1: (0, 0, 0), 三个开关都不按
按法2: (0, 0, 1), 按开关 1
按法3: (0, 1, 0), 按开关 2
按法4: (1, 0, 0), 按开关 3
按法5: (0, 1, 1), 按开关 1, 2
按法6: (1, 0, 1), 按开关 1, 3
按法7: (1, 1, 0), 按开关 2, 3
按法8: (1, 1, 1), 按开关 1, 2, 3

我们在决定当前的节点 u 怎么按开关的时候，目前我们考察的是如何按开关可以使得整个 u 对应的子树全都被熄灭。dp[left] 表示熄灭所有左子树所需的按开关次数、dp[right] 表示熄灭所有右子树所需的按开关次数。这样的话如果当前节点 u 是熄灭的，则当前节点不按动开关，dp[u] = dp[left] + dp[right]；如果 u 是开着的，则按动开关 1，dp[u] = dp[left] + dp[right] + 1。

但是很明显，一个节点上有 8 种按法，前面我们只考虑了按法 1 和 2。所以子树上还需要返回一些额外状态，这些状态使得我们可以通过 3 ~ 8 这几种按法使得 u 子树全都熄灭。现在的问题就是这些状态具体是哪些。

我们逆向分析，假设 u 子树已经全都熄灭了，看一下 3 ~ 8 这六种按动方法会使得 u 节点，以及 u 的各个子树变成什么状态。，结果如下：

1
2
3
4
5
6
按法3: u 节点及其子树全都亮
按法4: u 节点以及其子节点全都亮，u 的各个子树中除了子树的根以外全都灭
按法5: u 节点灭，u 的各个子树均亮
按法6: u 节点灭，u 的各个子节点亮，u 的各个子树中除了子树的根外全都灭
按法7: u 节点以及其子节点全都灭，u 的各个子树中除了子树的根以外全都亮
按法8: u 节点亮，u 的各个子节点灭，u 的各个子树中除了子树的根以外全都亮

之前我们只用到了【子树全都灭】这个状态，也就是 dp[v] 表示的是 u 的某个子树 v 全部熄灭所需次数。

现在我们要看一下上面这六种情况用到了子树的哪些状态，具体如下；

  • 按法 3 和 5 用到了【子树全都亮】这个状态，
  • 按法 4, 6 用到了【子树的根亮，其余节点灭】这个状态。
  • 按法 7, 8 用到了【子树的根灭，其余节点亮】这个状态。

把所有状态都考虑到以后，树形 DP 的算法如下，状态转移的部分应该是可以通过对称性减少一些的，这里就直接全部枚举了。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
状态设计
dp[u][s] := 当前的状态为 s 时，使得 u 子树全部熄灭所需的最少次数
            其中 s 状态共有 4 种
            s = 0:  子树 u 全都灭
            s = 1:  子树 u 全都亮
            s = 2:  子树 u 的根亮，其余节点全都灭
            s = 3:  子树 u 的根灭，其余节点全都亮

答案
dp[root][0]

初始化
dp[null][0..3] = 0

状态转移
(1) u 亮，则:
dp[u][0] = min( // 全灭
        1 + dp[left][0] + dp[right][0] # 按法 2
        1 + dp[left][1] + dp[right][1] # 按法 3
        1 + dp[left][2] + dp[right][2] # 按法 4
        3 + dp[left][3] + dp[right][3] # 按法 8
        )
dp[u][1] = min( // 全亮
        dp[left][1] + dp[right][1] # 按法 1
        2 + dp[left][0] + dp[right][0] # 按法 5
        2 + dp[left][3] + dp[right][3] # 按法 6
        2 + dp[left][2] + dp[right][2] # 按法 7
        )
dp[u][2] = min( // u 亮，其余全灭
        dp[left][0] + dp[right][0] # 按法 1
        2 + dp[left][1] + dp[right][1] # 按法 5
        2 + dp[left][2] + dp[right][2] # 按法 6
        2 + dp[left][3] + dp[right][3] # 按法 7
        )
dp[u][3] = min( // u 灭，其余全亮
        1 + dp[left][1] + dp[right][1] # 按法 2
        1 + dp[left][0] + dp[right][0] # 按法 3
        1 + dp[left][3] + dp[right][3] # 按法 4
        3 + dp[left][2] + dp[right][2] # 按法 8
        )
(1) u 灭，则:
dp[u][0] = min( // 全灭
        dp[left][0] + dp[right][0] # 按法 1
        2 + dp[left][1] + dp[right][1] # 按法 5
        2 + dp[left][2] + dp[right][2] # 按法 6
        2 + dp[left][3] + dp[right][3] # 按法 7
        )
dp[u][1] = min( // 全亮
        1 + dp[left][1] + dp[right][1] # 按法 2
        1 + dp[left][0] + dp[right][0] # 按法 3
        1 + dp[left][3] + dp[right][3] # 按法 4
        3 + dp[left][2] + dp[right][2] # 按法 8
        )
dp[u][2] = min( // u 亮，其余全灭
        1 + dp[left][0] + dp[right][0] # 按法 2
        1 + dp[left][1] + dp[right][1] # 按法 3
        1 + dp[left][2] + dp[right][2] # 按法 4
        3 + dp[left][3] + dp[right][3] # 按法 8
        )
dp[u][3] = min( // u 灭，其余全亮
        dp[left][1] + dp[right][1] # 按法 1
        2 + dp[left][0] + dp[right][0] # 按法 5
        2 + dp[left][3] + dp[right][3] # 按法 6
        2 + dp[left][2] + dp[right][2] # 按法 7
        )

代码 (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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    int closeLampInTree(TreeNode* root) {
        vector<int> dp = _postOrder(root);
        return dp[0];
    }

    vector<int> _postOrder(TreeNode* node)
    {
        if(!node)
            return {0, 0, 0, 0};
        vector<int> dp(4, INT_MAX);
        vector<int> dp_left = _postOrder(node -> left);
        vector<int> dp_right = _postOrder(node -> right);

        if(node -> val == 1)
        {
            // 全灭
            dp[0] = min(dp[0], 1 + dp_left[0] + dp_right[0]); // 按法 2
            dp[0] = min(dp[0], 1 + dp_left[1] + dp_right[1]); // 按法 3
            dp[0] = min(dp[0], 1 + dp_left[2] + dp_right[2]); // 按法 4
            dp[0] = min(dp[0], 3 + dp_left[3] + dp_right[3]); // 按法 8
             // 全亮
            dp[1] = min(dp[1], dp_left[1] + dp_right[1]); // 按法 1
            dp[1] = min(dp[1], 2 + dp_left[0] + dp_right[0]); // 按法 5
            dp[1] = min(dp[1], 2 + dp_left[3] + dp_right[3]); // 按法 6
            dp[1] = min(dp[1], 2 + dp_left[2] + dp_right[2]); // 按法 7
            // u 亮，其余全灭
            dp[2] = min(dp[2], dp_left[0] + dp_right[0]); // 按法 1
            dp[2] = min(dp[2], 2 + dp_left[1] + dp_right[1]); // 按法 5
            dp[2] = min(dp[2], 2 + dp_left[2] + dp_right[2]); // 按法 6
            dp[2] = min(dp[2], 2 + dp_left[3] + dp_right[3]); // 按法 7
            // u 灭，其余全亮
            dp[3] = min(dp[3], 1 + dp_left[1] + dp_right[1]); // 按法 2
            dp[3] = min(dp[3], 1 + dp_left[0] + dp_right[0]); // 按法 3
            dp[3] = min(dp[3], 1 + dp_left[3] + dp_right[3]); // 按法 4
            dp[3] = min(dp[3], 3 + dp_left[2] + dp_right[2]); // 按法 8
        }
        else
        {
            // 全灭
            dp[0] = min(dp[0], dp_left[0] + dp_right[0]); // 按法 1
            dp[0] = min(dp[0], 2 + dp_left[1] + dp_right[1]); // 按法 5
            dp[0] = min(dp[0], 2 + dp_left[2] + dp_right[2]); // 按法 6
            dp[0] = min(dp[0], 2 + dp_left[3] + dp_right[3]); // 按法 7
            // 全亮
            dp[1] = min(dp[1], 1 + dp_left[1] + dp_right[1]); // 按法 2
            dp[1] = min(dp[1], 1 + dp_left[0] + dp_right[0]); // 按法 3
            dp[1] = min(dp[1], 1 + dp_left[3] + dp_right[3]); // 按法 4
            dp[1] = min(dp[1], 3 + dp_left[2] + dp_right[2]); // 按法 8
            // u 亮，其余全灭
            dp[2] = min(dp[2], 1 + dp_left[0] + dp_right[0]); // 按法 2
            dp[2] = min(dp[2], 1 + dp_left[1] + dp_right[1]); // 按法 3
            dp[2] = min(dp[2], 1 + dp_left[2] + dp_right[2]); // 按法 4
            dp[2] = min(dp[2], 3 + dp_left[3] + dp_right[3]); // 按法 8
            // u 灭，其余全亮
            dp[3] = min(dp[3], dp_left[1] + dp_right[1]); // 按法 1
            dp[3] = min(dp[3], 2 + dp_left[0] + dp_right[0]); // 按法 5
            dp[3] = min(dp[3], 2 + dp_left[3] + dp_right[3]); // 按法 6
            dp[3] = min(dp[3], 2 + dp_left[2] + dp_right[2]); // 按法 7
        }
        return dp;
    }
};

算法2: 树形DP, 以祖先节点传递额外信息设计状态

刚刚我们是用的自底向上的思路，各个子树需要满足什么状态的时候，可以使得在当前节点 u 进行可能的 8 种按法后达到全灭的状态。

如果我们用自顶向下的思路，考虑根节点，如果它是灭的，那么按法 0, 5, 6, 7 可以使得它保持灭的状态，如果它是亮的那么按法 1, 2, 3, 8 可以把当前节点变为灭。

这样我们从根节点往下走，没走到一个节点，就考虑怎样操作可以把该节点变为灭，然后继续向下走。

对于任意一个节点，它有一个初始状态会影响该节点的动作选择，除此以外还会受到一些祖先节点的操作的影响。具体地就是取决于父节点是否启动了开关 3、以及父节点以及祖先节点的开关 2 的奇偶性。

因此在我们考虑一个节点需要哪种按法才能让该节点熄灭时，除了当前节点的灯是否亮，还需要知道其父节点是否按过开关 3、以及父节点和祖先节点按过开关 2 次数的奇偶性。

这样可以得到我们的树形 DP 算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
状态定义：
dp[u][s1][s2] := 父节点按开关 3 的情况为 s1, 祖先节点按开关 2 的奇偶性为 s2 时，将 u 子树全部熄灭所需的最少次数

答案:
dp[root][0][0]

初始化:
dp[null][0..1][0..1] = 0

状态转移:
(1) u 亮 ^ s1 ^ s2 为 1，这种情况下只能选按法 2, 3, 4, 8
dp[u][s1][s2] = min(
        dp[left][0][s2] + dp[right][0][s2] // 按法 2
        dp[left][1][s2] + dp[right][1][s2] // 按法 3
        dp[left][0][s2 ^ 1] + dp[right][0][s2 ^ 1] // 按法 4
        dp[left][1][s2 ^ 1] + dp[right][1][s2 ^ 1] // 按法 8
        )
(2) u 亮 ^ s1 ^ s2 为 0，这种情况下只能选按法 1, 5, 6, 7
dp[u][s1][s2] = min(
        dp[left][0][s2] + dp[right][0][s2] // 按法 1
        dp[left][0][s2 ^ 1] + dp[right][0][s2 ^ 1] // 按法 5
        dp[left][1][s2] + dp[right][1][s2] // 按法 6
        dp[left][1][s2 ^ 1] + dp[right][1][s2 ^ 1] // 按法 7
        )

代码(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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    int closeLampInTree(TreeNode* root) {
        idx = unordered_map<TreeNode*, int>();
        idx[nullptr] = 0;
        get_idx(root);
        int n = idx.size();
        dp = vector<vector<vector<int>>>(n, vector<vector<int>>(2, vector<int>(2, -1)));
        return _preOrder(root, 0, 0);
    }

    unordered_map<TreeNode*, int> idx; // 节点的编号
    vector<vector<vector<int>>> dp;

    void get_idx(TreeNode* node)
    {
        int i = idx.size();
        idx[node] = i;
        if(node -> left)
            get_idx(node -> left);
        if(node -> right)
            get_idx(node -> right);
    }

    int _preOrder(TreeNode* node, int s1, int s2)
    {
        if(dp[idx[node]][s1][s2] != -1)
            return dp[idx[node]][s1][s2];
        if(!node)
            return dp[idx[node]][s1][s2] = 0;
        int res = INT_MAX;
        if(((node -> val) ^ s1 ^ s2) == 1)
        {
            int res2 = 1 + _preOrder(node -> left, 0, s2) + _preOrder(node -> right, 0, s2); // 按法 2
            int res3 = 1 + _preOrder(node -> left, 1, s2) + _preOrder(node -> right, 1, s2); // 按法 3
            int res4 = 1 + _preOrder(node -> left, 0, s2 ^ 1) + _preOrder(node -> right, 0, s2 ^ 1); // 按法 4
            int res8 = 3 + _preOrder(node -> left, 1, s2 ^ 1) + _preOrder(node -> right, 1, s2 ^ 1); // 按法 8
            res = min(res, res2);
            res = min(res, res3);
            res = min(res, res4);
            res = min(res, res8);
        }
        else
        {
            int res1 = _preOrder(node -> left, 0, s2) + _preOrder(node -> right, 0, s2); // 按法 1
            int res5 = 2 + _preOrder(node -> left, 0, s2 ^ 1) + _preOrder(node -> right, 0, s2 ^ 1); // 按法 5
            int res6 = 2 + _preOrder(node -> left, 1, s2) + _preOrder(node -> right, 1, s2); // 按法 6
            int res7 = 2 + _preOrder(node -> left, 1, s2 ^ 1) + _preOrder(node -> right, 1, s2 ^ 1); // 按法 7
            res = min(res, res1);
            res = min(res, res5);
            res = min(res, res6);
            res = min(res, res7);
        }
        return dp[idx[node]][s1][s2] = res;
    }
};
Share