算法疑难杂症

力扣LCP34-二叉树染色

字数统计: 581字   |   阅读时长: 2分
, ,

摘要: LCP34，树形DP

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

今天我们来看一个树形DP的何题，力扣 LCP34，本题是2021力扣杯春季赛团队赛第2题。算法要点如下：

题目

小扣有一个根结点为 root 的二叉树模型，初始所有结点均为白色，可以用蓝色染料给模型结点染色，模型的每个结点有一个 val 价值。小扣出于美观考虑，希望最后二叉树上每个蓝色相连部分的结点个数不能超过 k 个，求所有染成蓝色的结点价值总和最大是多少？

提示：

1
2
3
1 <= k <= 10
1 <= val <= 10000
1 <= 结点数量 <= 10000

示例 1：
输入：root = [5,2,3,4], k = 2
输出：12
解释：结点 5、3、4 染成蓝色，获得最大的价值 5+3+4=12

示例 2：
输入：root = [4,1,3,9,null,null,2], k = 2
输出：16
解释：结点 4、3、9 染成蓝色，获得最大的价值 4+3+9=16

题解

算法：树形DP

二叉树后序遍历/树形DP

1
2
3
4
5
dp[u][k] := 以 u 为根，且与 u 相连的蓝色节点有 k 个时的最大分数

dp[u][0] = max(dp[left][...]) + max(dp[right][...])
dp[u][j] = max(dp[left][l] + dp[right][r] + u.val)
    其中 j = l + r + 1, 1 <= j <= k

代码 (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
class Solution {
public:
    int maxValue(TreeNode* root, int k) {
        vector<int> result = _postOrder(root, k);
        return *max_element(result.begin(), result.end());
    }

private:
    vector<int> _postOrder(TreeNode* node, const int k)
    {
        if(!node)
            return vector<int>(k + 1);
        vector<int> result_left = _postOrder(node -> left, k);
        vector<int> result_right = _postOrder(node -> right, k);

        vector<int> result(k + 1);
        for(int j = 1; j <= k; ++j)
        {
            for(int l = 0; l <= j - 1; ++l)
            {
                int r = j - 1 - l;
                result[j] = max(result[j], result_left[l] + result_right[r] + node -> val);
            }
        }
        int max_l = 0, max_r = 0;
        for(int l = 0; l <= k; ++l)
            max_l = max(max_l, result_left[l]);
        for(int r = 0; r <= k; ++r)
            max_r = max(max_r, result_right[r]);
        result[0] = max_l + max_r;
        return result;
    }
};
Share