动态规划之树形DP

这篇具有很好参考价值的文章主要介绍了动态规划之树形DP。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

树形DP

何为树形DP

树形DP是指在“树”这种数据结构上进行的动态规划:给出一颗树,要求以最少的代价(或取得最大收益)完成给定的操作。通常这类问题规模比较大,枚举算法效率低,无法胜任,贪心算法不能求得最优解,因此需要用动态规划进行求解。

在树上做动态规划显得非常合适,因为树本身有“子结构”性质(树和子树),具有递归性,符合DP性质。相比线性DP,树形DP的状态转移方程更加直观。

树形动态规划(Tree DP)是一种动态规划算法,在处理树状结构(例如树、森林、有向无环图等)上的问题时非常常见和有效。树形动态规划通过将问题拆解为子问题,并利用子问题的解来求解更大规模的问题。

在树形动态规划中,我们需要定义一个适合的状态和状态转移方程。一般来说,状态可以定义为以当前节点为根的子树的某种性质,例如最大路径和、最长路径长度、最大权值和等等。而状态转移方程则描述了如何由子节点的状态计算当前节点的状态。

树形动态规划的典型做法是使用深度优先搜索(DFS)遍历整个树,在遍历过程中进行状态的计算和更新。通过递归地计算子节点的状态,并将其传递给父节点,可以得到整个树的最终状态。

在实现树形动态规划时,需要注意避免重复计算,可以使用记忆化搜索或者自底向上的方式进行计算。此外,还要注意选择合适的遍历顺序,以保证子问题的状态在计算当前节点状态时已经求解完毕。

总而言之,树形动态规划是一种针对树状结构问题的动态规划算法,通过拆解问题为子问题,并利用子问题的解求解更大规模的问题。它在解决树相关的问题时具有重要的应用价值。

树形DP例题

HDU-1520 Anniversary party

HDU-1520 Anniversary party

树形dp,动态规划,算法,c++

题目大意

邀请员工参加party,但是为了避免员工和直属上司发生尴尬,规定员工和直属上司不能同时出席。

也就是每个人代表树中一个结点,每个结点拥有一个权值,相邻的父结点和子结点只能选择一个,问如何取才能使总权值之和最大。

员工编号从1到N。第一行输入包含数字N。1 < = N < = 6000。随后的N行中的每一行都包含相应员工的愉快度评级。欢乐评级是一个介于-128到127之间的整数。然后是描述主管关系树的T行。树规范的每一行都具有以下形式: L K 这意味着第K个员工是第L个员工的直接主管。输入以一行结束 0 0

解题思路

根据DP的解题思路,定义状态为:

d p [ i ] [ 0 ] dp[i][0] dp[i][0],表示不选择当前结点时候的最优解

d p [ i ] [ 1 ] dp[i][1] dp[i][1],表示选择当前结点时候的最优解

其中状态转移方程分为下面两种情况:

  1. 不选择当前结点,则子结点可选可不选,取其中的最大值即可,也就是 d p [ u ] [ 0 ] + = m a x ( d p [ s o n ] [ 0 ] , d p [ s o n ] [ 1 ] ) dp[u][0] += max(dp[son][0], dp[son][1]) dp[u][0]+=max(dp[son][0],dp[son][1])
  2. 选择当前结点,则其子结点不能选, d p [ u ] [ 1 ] + = d p [ s o n ] [ 0 ] dp[u][1] += dp[son][0] dp[u][1]+=dp[son][0]

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 6010;
vector<int>tree[maxn];
int dp[maxn][2], father[maxn], value[maxn];
void dfs(int u) {
    dp[u][0] = 0; // 不参加party
    dp[u][1] = value[u]; // 参加party
    for(int i = 0; i < tree[u].size(); i++) {
        int son = tree[u][i];
        dfs(son); // 深搜子结点
        dp[u][0] += max(dp[son][0], dp[son][1]); // 父结点不选,子结点可选可不选
        dp[u][1] += dp[son][0]; // 父结点选择,子结点不能选
    }
}
int main() {
    int n, a, b;
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; i++) {
            scanf("%d", &value[i]);
            tree[i].clear();
            father[i] = -1;
        }
        memset(dp, 0, sizeof(dp));
        while(true) { // 建树
            scanf("%d%d", &a, &b);
            if(a == 0 && b == 0) break;
            tree[b].push_back(a);
            father[a] = b; // 父子关系,表示a的父亲是b
        }
        for(int i = 1; i <= n; i++) {
            if(father[i] == -1) { // 寻找父结点,从父结点开始深搜
                dfs(i);
                printf("%d\n", max(dp[i][0], dp[i][1]));
                break;
            }
        }
    }
    return 0;
}

HDU-2196 Computer

HDU-2196 Computer

树形dp,动态规划,算法,c++

题目大意

一颗树,根节点的编号是1,对其中的任意一个结点,求离这个结点最远结点的距离。

输入包含多个测试用例,每个用例的第一行是一个自然数N,N不超过10000,接下来N-1行,每行输入两个整数:第一个整数为某结点id,第二个整数为连接到这个结点需要的距离。

输出N行,表示距离第i个结点的最远距离

解题思路

对于求解距离某结点的最长距离,应当分为两种情况:

对于任意一个结点

  1. 结点 i i i 的子树中的结点距离结点 i i i 的最长距离,而为了方便第二种情况的计算,第一次深搜的时候需要记录结点 i i i 的子树中某个结点到该结点的最长距离和第二长的距离。

  2. 第二种情况就是结点 i i i 往上走,而此时往上走又分为两种情况:

    从结点 i i i 往上继续走,没有走结点 i i i 的父结点到其子树的最长距离的路径

    若结点 i i i 沿着其父结点的最长路径上走时,则需考虑结点 i i i 是否在其父结点的最长子树上,此时则需要用到最初求得各个结点到其它结点的最长距离和次长距离,如果结点 i i i 在其父结点的最长子树上那么 X = two + dist(i, i 的父结点),否则 X = one + dist(i, i 的父结点)

综上所述,第一种情况和第二种情况求得两个值的最大值即为答案

状态的设计:结点 i i i 的子树到 i i i 的最长距离 d p [ i ] [ 0 ] dp[i][0] dp[i][0] 以及次长距离 d p [ i ] [ 1 ] dp[i][1] dp[i][1],从结点 i i i 往上走的最长距离 d p [ i ] [ 2 ] dp[i][2] dp[i][2]

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int id; // 子树结点编号
    int cost;
};
const int maxn = 10010;
int dp[maxn][3], n;
vector <Node> tree[maxn];
void init() { // 初始化和建树
    for(int i = 1; i <= n; i++) tree[i].clear();
    memset(dp, 0, sizeof(dp));
    int x, y;
    for(int i = 2; i <= n; i++) {
        scanf("%d%d", &x, &y);
        Node tmp;
        tmp.id = i;
        tmp.cost = y;
        tree[x].push_back(tmp);
    }
}
void dfs1(int father) { // 搜索以结点father为起点到子树的最长距离和次长距离
    int one = 0, two = 0; // one 记录father往下走的最长距离,two记录次长距离
    for(int i = 0; i < tree[father].size(); i++) { // 先处理子结点再处理父结点
        Node child = tree[father][i];
        dfs1(child.id); // 递归子结点,直到最底层
        int temp = child.cost + dp[child.id][0];
        if(temp >= one) {
            two = one;
            one = temp;
        }
        if(temp < one && temp > two) two = temp;
    }
    dp[father][0] = one; // 得到以father为起点的子树的最长距离
    dp[father][1] = two; // 得到以father为起点的子树的次长距离
}
void dfs2(int father) { // 先处理父结点再处理子结点
    for(int i = 0; i < tree[father].size(); i++) {
        Node child = tree[father][i];
        if(child.cost + dp[child.id][0] == dp[father][0]) // child在最长距离的子树上
            dp[child.id][2] = max(dp[father][1], dp[father][2]) + child.cost;
        else dp[child.id][2] = max(dp[father][0], dp[father][2]) + child.cost; //否则
        dfs2(child.id);
    }
}
int main() {
    while(~scanf("%d", &n)) {
        init();
        dfs1(1);
        dp[1][2] = 0;
        dfs2(1);
        for(int i = 1; i <= n; i++) {
            printf("%d\n", max(dp[i][0], dp[i][2]));
        }
    }
    return 0;
}

834. 树中距离之和

834. 树中距离之和

给定一个无向、连通的树。树中有 n 个标记为 0...n-1 的节点以及 n-1 条边 。

给定整数 n 和数组 edgesedges[i] = [ai, bi]表示树中的节点 aibi 之间有一条边。

返回长度为 n 的数组 answer ,其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。

示例 1:

树形dp,动态规划,算法,c++

输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 树如图所示。
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此,answer[0] = 8,以此类推。

参考灵神的题解写出来的,不得不说灵神 yyds,比官方给出的题解简单多了。

灵神的题解地址:传送门

灵神给出的解题思路如下图所示:

树形dp,动态规划,算法,c++

AC代码:文章来源地址https://www.toymoban.com/news/detail-744936.html

class Solution {
public:
    static const int maxn = 3e4 + 10;
    vector<int>tree[maxn];
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        for(auto edge : edges) {
            tree[edge[0]].push_back(edge[1]);
            tree[edge[1]].push_back(edge[0]);
        }
        vector<int>ans(n);
        vector<int>children(n, 1); // 每颗子树所包含结点数量
        function<void(int, int, int)> dfs1 = [&](int child, int father, int depth) {
            ans[0] += depth;
            for(auto i : tree[child]) {
                if(i != father) { // 避免访问父结点
                    dfs1(i, child, depth + 1);
                    children[child] += children[i]; // 累加子树大小
                }
            }
        };
        dfs1(0, -1, 0); // 0 没有父结点
        function<void(int, int)> dfs = [&](int child, int father) {
            for(auto i : tree[child]) {
                if(i != father) {
                    ans[i] += (ans[child] + n - children[i] * 2);
                    dfs(i, child);
                }
            }
        };
        dfs(0, -1);
        return ans;
    }
};

到了这里,关于动态规划之树形DP的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划-树形DP

    链接:https://www.acwing.com/problem/content/848/ 给定一颗树,树中包含 n n n 个结点(编号 1 ∼ n 1 sim n 1 ∼ n )和 n − 1 n-1 n − 1 条无向边。 请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。 重心定义:重心是指树中的一个结点,如果将这个点删除后,剩

    2024年02月08日
    浏览(37)
  • 动态规划——树形DP 学习笔记

    前置知识:树基础。 树形 DP,即在树上进行的 DP,最常见的状态表示为 (f_{u,cdots}) ,表示以 (u) 为根的子树的某个东东。 本文将讲解一些经典题目(树的子树个数、树的最大独立集、树的最小点覆盖、树的最小支配集、树的直径、树的重心、树的中心),以及一些常见形

    2024年02月08日
    浏览(37)
  • 动态规划树形DP课后习题蓝桥舞会

      蓝桥舞会 题目描述 蓝桥公司一共有n名员工,编号分别为1~n。 他们之间的关系就像一棵以董事长为根的树,父节点就是子节点的直接上司。每个员工有一个快乐指数aj。 现蓝桥董事会决定举办一场蓝桥舞会来让员工们在工作之余享受美好时光,不过对于每个员工,他们都

    2024年02月21日
    浏览(43)
  • 动态规划day09(打家劫舍,树形dp)

    目录 198.打家劫舍 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难 213.打家劫舍II 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难 337.打家劫舍 III(树形dp) 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中

    2024年01月23日
    浏览(91)
  • 11.动态规划:树形DP问题、树上最大独立集、树上最小支配集、换根DP、树上倍增(LCA)【灵神基础精讲】

    回溯和树形DP的区别(什么时候需要return结果?):对于回溯,通常是在「递」的过程中增量地构建答案,并在失败时能够回退,例如八皇后。对于递归,是把原问题分解为若干个相似的子问题,通常会在「归」的过程中有一些计算。如果一个递归能考虑用记忆化来优化,就

    2024年02月04日
    浏览(40)
  • 【LeetCode动态规划#11】打家劫舍系列题(涉及环结构和树形DP的讨论)

    力扣题目链接(opens new window) 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非

    2023年04月21日
    浏览(36)
  • DP算法:动态规划算法

    (1)确定初始状态 (2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来 (3)确定边界条件。 蓝桥杯——印章(python实现) 使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率 i表示买的印章数,j表示凑齐的印章种数 情况一:如果ij,不可能凑齐印章,概

    2024年02月07日
    浏览(49)
  • 算法——动态规划(DP)——递推

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年01月20日
    浏览(55)
  • ★动态规划(DP算法)详解

    什么是动态规划:动态规划_百度百科 内容太多了不作介绍,重点部分是无后效性,重叠子问题,最优子结构。 问S-P1和S-P2有多少种路径数,毫无疑问可以先从S开始深搜两次,S-P1和S-P2找出所有路径数,但是当这个图足够大,那就会超时。 动态规划旨在用 空间换时间 ,我们

    2024年02月04日
    浏览(48)
  • 动态规划(DP)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 动态规划(Dynamic Programming,DP)是一种用来解决一类最优化问题的算法思想。简单来说,动态规划将一个复杂的问题分解成若干个子

    2024年02月05日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包