04.09_树形dp
树形 DP
问题描述
树形动态规划是指在树结构上进行状态转移的问题。
常见的有树的最大独立集、树的直径等。
通常需要定义状态表示树上某个节点的最优解。
树的最大独立集
算法思想
- 定义dp[i][0/1]表示以i为根的子树中，不选/选择i节点的最大独立集大小
- 如果选择当前节点，则子节点不能选
- 状态转移方程：
- dp[i][0] = sum(max(dp[j][0], dp[j][1])) 其中j是i的子节点
- dp[i][1] = 1 + sum(dp[j][0]) 其中j是i的子节点
- 最终答案为max(dp[root][0], dp[root][1])
代码实现
class Solution {
vector<vector<int>> dp;
vector<vector<int>> g;
void dfs(int u, int fa) {
dp[u][1] = 1; // 选择当前节点
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]); // 不选当前节点
dp[u][1] += dp[v][0]; // 选择当前节点
}
}
public:
int maxIndependentSet(int n, vector<vector<int>>& edges) {
dp.assign(n, vector<int>(2, 0));
g.assign(n, vector<int>());
for (auto& e : edges) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
dfs(0, -1);
return max(dp[0][0], dp[0][1]);
}
};
class Solution {
int[][] dp;
List<Integer>[] g;
void dfs(int u, int fa) {
dp[u][1] = 1; // 选择当前节点
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
dp[u][0] += Math.max(dp[v][0], dp[v][1]); // 不选当前节点
dp[u][1] += dp[v][0]; // 选择当前节点
}
}
public int maxIndependentSet(int n, int[][] edges) {
dp = new int[n][2];
g = new List[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>();
}
for (int[] e : edges) {
g[e[0]].add(e[1]);
g[e[1]].add(e[0]);
}
dfs(0, -1);
return Math.max(dp[0][0], dp[0][1]);
}
}
def maxIndependentSet(n: int, edges: List[List[int]]) -> int:
dp = [[0] * 2 for _ in range(n)]
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
def dfs(u: int, fa: int) -> None:
dp[u][1] = 1 # 选择当前节点
for v in g[u]:
if v == fa: continue
dfs(v, u)
dp[u][0] += max(dp[v][0], dp[v][1]) # 不选当前节点
dp[u][1] += dp[v][0] # 选择当前节点
dfs(0, -1)
return max(dp[0][0], dp[0][1])
树的直径
算法思想
- 定义dp[i]表示以i为根的子树中，从i到叶子节点的最长路径长度
- 对于每个节点，考虑通过它的最长路径
- 状态转移方程：dp[i] = max(dp[j] + w) 其中j是i的子节点，w是边权
- 最终答案为max(dp[i] + dp[j]) 其中i,j是相邻节点
代码实现
class Solution {
vector<int> dp;
vector<vector<pair<int, int>>> g;
int ans = 0;
void dfs(int u, int fa) {
int max1 = 0, max2 = 0; // 最长和次长路径
for (auto [v, w] : g[u]) {
if (v == fa) continue;
dfs(v, u);
int len = dp[v] + w;
if (len > max1) {
max2 = max1;
max1 = len;
} else if (len > max2) {
max2 = len;
}
}
dp[u] = max1; // 从u到叶子的最长路径
ans = max(ans, max1 + max2); // 通过u的最长路径
}
public:
int treeDiameter(int n, vector<vector<int>>& edges) {
dp.assign(n, 0);
g.assign(n, vector<pair<int, int>>());
for (auto& e : edges) {
g[e[0]].emplace_back(e[1], 1);
g[e[1]].emplace_back(e[0], 1);
}
dfs(0, -1);
return ans;
}
};
class Solution {
int[] dp;
List<int[]>[] g;
int ans = 0;
void dfs(int u, int fa) {
int max1 = 0, max2 = 0; // 最长和次长路径
for (int[] e : g[u]) {
int v = e[0], w = e[1];
if (v == fa) continue;
dfs(v, u);
int len = dp[v] + w;
if (len > max1) {
max2 = max1;
max1 = len;
} else if (len > max2) {
max2 = len;
}
}
dp[u] = max1; // 从u到叶子的最长路径
ans = Math.max(ans, max1 + max2); // 通过u的最长路径
}
public int treeDiameter(int n, int[][] edges) {
dp = new int[n];
g = new List[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>();
}
for (int[] e : edges) {
g[e[0]].add(new int[]{e[1], 1});
g[e[1]].add(new int[]{e[0], 1});
}
dfs(0, -1);
return ans;
}
}
def treeDiameter(n: int, edges: List[List[int]]) -> int:
dp = [0] * n
g = [[] for _ in range(n)]
ans = 0
for u, v in edges:
g[u].append((v, 1))
g[v].append((u, 1))
def dfs(u: int, fa: int) -> None:
nonlocal ans
max1 = max2 = 0 # 最长和次长路径
for v, w in g[u]:
if v == fa: continue
dfs(v, u)
length = dp[v] + w
if length > max1:
max2 = max1
max1 = length
elif length > max2:
max2 = length
dp[u] = max1 # 从u到叶子的最长路径
ans = max(ans, max1 + max2) # 通过u的最长路径
dfs(0, -1)
return ans
时间复杂度分析
| 树的最大独立集 | ||
| 树的直径 |
应用场景
- 树的最大独立集
- 树的直径问题
- 树的中心问题
- 树的最小支配集
- 树的最小覆盖
注意事项
- 状态定义的选择
- 子树信息的维护
- 递归实现的正确性
- 边界条件的处理
- 路径信息的更新
投递蔚来等公司8个岗位 >
老板电器公司氛围 78人发布