2022力扣秋季赛第4题

  |  

摘要: 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