树状动态规划

树型动态规划是一类用于树形结构问题的动态规划技术，通常用于解决涉及树（如二叉树、通用树等）的问题。它的基本思想是利用递归和子问题的结果来构建整个问题的解。树型动态规划在树的每个节点上进行状态转移，通常通过后序遍历（Postorder Traversal）从叶子节点到根节点计算子问题的最优解，再逐步合并这些子问题的解以得到整个树的最优解。

典型应用场景

树的最小路径和问题：在树中找到从根节点到叶子节点的最小路径和。
树的直径问题：计算树中两个节点之间的最长路径。
树的子树最大值问题：找出每个节点作为根节点的子树中的最大值。
树的覆盖问题：例如在树上安装摄像头的问题，需要最小数量的摄像头覆盖所有节点。

关键步骤

状态定义：定义在树的每个节点处需要存储的信息。通常，这包括当前节点和子节点相关的最优值。
状态转移方程：根据树的结构定义如何从子节点的状态合并成当前节点的状态。例如，如果你想在树中找到最大路径和，状态转移方程可能会涉及到将子节点的最大路径和与当前节点的值相加。
边界条件：确定树的叶子节点的状态。这通常是动态规划的初始条件。
遍历顺序：通常使用后序遍历，因为需要先计算子节点的值再计算父节点的值。

代码演示：

/**************************************************************** 
 * Description: treeDP
1、输入：树的边信息。
2、dfs函数：计算以每个节点为根的子树的最大深度，并更新经过该节点的最大路径。
3、状态：dp[u] 存储以节点 u 为中心的最长路径。
4、结果：树的直径可以通过计算所有节点的 dp[u] 中的最大值来得到。
 * Author: Alex Li
 * Date: 2024-08-14 13:57:42
 * LastEditTime: 2024-08-14 13:57:57
****************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> tree;
vector<int> dp;

// 辅助函数：计算以节点 u 为根的子树的最大深度，并更新树的直径
int dfs(int u, int parent) {
    int max1 = 0, max2 = 0;  // 记录两个最大的子树深度
    for (int v : tree[u]) {
        if (v == parent) continue;
        int depth = dfs(v, u) + 1;
        if (depth > max1) {
            max2 = max1;
            max1 = depth;
        } else if (depth > max2) {
            max2 = depth;
        }
    }
    dp[u] = max1 + max2;  // 更新经过节点 u 的最大路径
    return max1;  // 返回该子树的最大深度
}

int main() {
    int n;
    cin >> n;
    tree.resize(n);
    dp.resize(n, 0);

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dfs(0, -1);

  //  int diameter = *max_element(dp.begin(), dp.end());
     int diameter = 0;
    for (int i = 0; i < n; ++i) {
        diameter = max(diameter, dp[i]);
    }
    cout << "Tree Diameter: " << diameter << endl;

    return 0;
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

树状动态规划

典型应用场景

关键步骤