前期知識
最大獨立集 需要從圖中選擇盡量多的點，使得這些點互不相鄰。
例題
337. 打家劫舍 III
337. 打家劫舍 III
用一個數(shù)組 int[] = {a, b} 來接收每個節(jié)點返回的結(jié)果。返回值{a,b} a表示沒選當(dāng)前節(jié)點的最大值,b表示選了當(dāng)前節(jié)點的最大值。
使用后序遍歷dfs。 （發(fā)現(xiàn)樹形 DP 基本都是后序 dfs）
class Solution {
public int rob(TreeNode root) {
int[] res = dfs(root);
return Math.max(res[0], res[1]);
}
public int[] dfs(TreeNode root) {
// 返回值{a,b} a表示沒選當(dāng)前節(jié)點的最大值,b表示選了當(dāng)前節(jié)點的最大值
if (root == null) return new int[]{0, 0};
int[] l = dfs(root.left), r = dfs(root.right);
int a = Math.max(l[0], l[1]) + Math.max(r[0], r[1]), b = root.val + l[0] + r[0];
return new int[]{a, b};
}
}
相關(guān)練習(xí)題目
沒有上司的舞會 https://www.luogu.com.cn/problem/P1352
P1352 沒有上司的舞會
這道題目相當(dāng)于每個節(jié)點可能會有若干個子節(jié)點的 337. 打家劫舍 III 。
因為是 ACM 模式，所以代碼處理輸入很冗長。
AC代碼如下：
import java.util.*;
public class Main {
static List<Integer>[] childs; // 記錄每個節(jié)點的子節(jié)點列表
static int[] r; // 記錄每個節(jié)點的快樂指數(shù)
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
r = new int[n + 1];
for (int i = 1; i <= n; ++i) r[i] = scanner.nextInt();
childs = new ArrayList[n + 1];
Arrays.setAll(childs, e -> new ArrayList());
Set<Integer> s = new HashSet<>(); // 記錄哪些節(jié)點沒有父節(jié)點，把他們統(tǒng)一放在0節(jié)點之下
for (int i = 1; i <= n; ++i) s.add(i);
for (int i = 2; i <= n; ++i) {
int l = scanner.nextInt(), k = scanner.nextInt();
childs[k].add(l);
s.remove(l);
}
for (int v: s) childs[0].add(v); // 所有沒有父節(jié)點的節(jié)點放在0節(jié)點之下
int[] res = dfs(0);
System.out.println(Math.max(res[0], res[1]));
return;
}
public static int[] dfs(int rootId) {
int a = 0, b = r[rootId]; // a表示不選當(dāng)前節(jié)點，b表示選當(dāng)前節(jié)點
for (int i: childs[rootId]) { // 枚舉所有子節(jié)點
int[] res = dfs(i);
a += Math.max(res[0], res[1]); // 不選當(dāng)前節(jié)點，所以子節(jié)點選不選都可以
b += res[0]; // 選當(dāng)前節(jié)點，所以子節(jié)點只能不選
}
return new int[]{a, b};
}
}
從代碼模板來看，這里使用 for 循環(huán)來枚舉當(dāng)前節(jié)點的所有子節(jié)點。
1377. T 秒后青蛙的位置 https://leetcode.cn/problems/frog-position-after-t-seconds/???
1377. T 秒后青蛙的位置
解法1：BFS
從題意來看，每次青蛙都會往下走一層，很像層序遍歷，所以可以是用 bfs 來模擬整個過程。
在 bfs 的過程中，如果當(dāng)前節(jié)點的概率為 p，他有 k 個子節(jié)點，那么它的所有子節(jié)點的概率就是 p / k，即在分母上乘了 k。
在這個過程中，我們可以記錄各個節(jié)點的概率分母。
如果當(dāng)前節(jié)點沒有子節(jié)點，那么它的概率不變，再重新加入隊列中。
class Solution {
public double frogPosition(int n, int[][] edges, int t, int target) {
// 建樹
List<Integer>[] g = new ArrayList[n + 1];
Arrays.setAll(g, e -> new ArrayList());
for (int[] edge: edges) {
int x = edge[0], y = edge[1];
g[x].add(y);
g[y].add(x);
}
boolean[] st = new boolean[n + 1];
// 由于某些樣例在計算概率分母時會溢出int，因此使用long
Queue<long[]> q = new LinkedList();
q.offer(new long[]{1, 1}); // 將第一個節(jié)點放入隊列
st[1] = true;
for (int i = 0; i <= t; ++i) {
int sz = q.size();
for (int j = 0; j < sz; ++j) {
long[] cur = q.poll();
// 如果達(dá)到了目標(biāo)位置且時間正確，返回答案
if (cur[0] == target && i == t) return 1.0 / cur[1];
List<Integer> children = g[(int)cur[0]];
boolean f = false; // 記錄它是否有子節(jié)點
int cnt = 0; // 記錄它有幾個子節(jié)點
for (int child: children) {
if (!st[child]) ++cnt;
}
for (int child: children) {
if (!st[child]) {
q.offer(new long[]{child, cur[1] * cnt}); // 將子節(jié)點加入隊列，概率的分母更新為cnt[1]*cnt
st[child] = true;
f = true; // 說明有子節(jié)點
}
}
// 如果當(dāng)前節(jié)點沒有子節(jié)點，那么它還會待在當(dāng)前位置
if (!f) q.offer(cur);
}
}
return 0;
}
}
優(yōu)化代碼
優(yōu)化的點包括：
- 修改了 return 結(jié)果的判斷條件
- 刪去了 cnt 統(tǒng)計每個節(jié)點的子節(jié)點個數(shù)，因為子節(jié)點數(shù)目就是g[x].size() - 1
- 給起始節(jié)點1增加一個父節(jié)點0，可以避免寫多余判斷
class Solution {
public double frogPosition(int n, int[][] edges, int t, int target) {
// 建樹
List<Integer>[] g = new ArrayList[n + 1];
Arrays.setAll(g, e -> new ArrayList());
g[1].add(0); // 小技巧
for (int[] edge: edges) {
int x = edge[0], y = edge[1];
g[x].add(y);
g[y].add(x);
}
boolean[] st = new boolean[n + 1];
// 由于某些樣例在計算概率分母時會溢出int，因此使用long
Queue<long[]> q = new LinkedList();
q.offer(new long[]{1, 1}); // 將第一個節(jié)點放入隊列
st[1] = true;
for (int i = 0; i <= t; ++i) {
int sz = q.size();
for (int j = 0; j < sz; ++j) {
long[] cur = q.poll();
// 如果達(dá)到了目標(biāo)位置且時間正確，返回答案
if (cur[0] == target) {
if (i == t || g[(int)cur[0]].size() == 1) return 1.0 / cur[1];
return 0;
}
List<Integer> children = g[(int)cur[0]];
int cnt = children.size() - 1; // 記錄它有幾個子節(jié)點
for (int child: children) {
if (!st[child]) {
q.offer(new long[]{child, cur[1] * cnt}); // 將子節(jié)點加入隊列，概率的分母更新為cnt[1]*cnt
st[child] = true;
}
}
}
}
return 0;
}
}
解法2——自頂向下dfs
整體思路與 bfs 類似。
class Solution {
double ans;
public double frogPosition(int n, int[][] edges, int t, int target) {
// 建樹
List<Integer>[] g = new ArrayList[n + 1];
Arrays.setAll(g, e -> new ArrayList());
g[1].add(0); // 常用技巧：為了減少額外判斷,給1加個父節(jié)點0
for (int[] edge: edges) {
int x = edge[0], y = edge[1];
g[x].add(y);
g[y].add(x);
}
dfs(g, target, 1, 0, t, 1);
return ans;
}
public boolean dfs(List<Integer>[] g, int target, int x, int father, int leftTime, long prod) {
// 如果x == target 且 （正好在t秒或處在葉子節(jié)點上）
if (x == target && (leftTime == 0 || g[x].size() == 1)) {
ans = 1.0 / prod;
return true;
}
if (x == target || leftTime == 0) return false;
for (int y: g[x]) { // 遍歷x的兒子y
if (y != father && dfs(g, target, y, x, leftTime - 1, prod * (g[x].size() - 1))) {
return true; // 找到了就不再遞歸了
}
}
return false;
}
}
這里學(xué)到的重要技巧：
- 每個節(jié)點只會有一個父節(jié)點，因此它的子節(jié)點數(shù)量就是
g[x].size() - 1，不需要單獨計算了。 - g[1].add(0); // 常用技巧：為了減少額外判斷,給1加個父節(jié)點0
- dfs 返回 boolean 值，在 if () 中進行 dfs。
解法3——自底向上dfs
class Solution {
double ans;
public double frogPosition(int n, int[][] edges, int t, int target) {
// 建樹
List<Integer>[] g = new ArrayList[n + 1];
Arrays.setAll(g, e -> new ArrayList());
g[1].add(0); // 為了減少額外判斷,給1加個父節(jié)點0
for (int[] edge: edges) {
int x = edge[0], y = edge[1];
g[x].add(y);
g[y].add(x);
}
long prod = dfs(g, target, 1, 0, t);
return prod == 0? prod: 1.0 / prod;
}
public long dfs(List<Integer>[] g, int target, int x, int father, int leftTime) {
// 找到結(jié)果的兩種情況
if (leftTime == 0) return x == target? 1: 0;
if (x == target) return g[x].size() == 1? 1: 0;
// 遍歷 x 的兒子 y
for (int y: g[x]) {
if (y != father) {
long prod = dfs(g, target, y, x, leftTime - 1);
if (prod != 0) return prod * (g[x].size() - 1);
}
}
return 0;
}
}
自底向上的優(yōu)點在于，只有找到了 target 之后才會做乘法計算 prod。
2646. 最小化旅行的價格總和 https://leetcode.cn/problems/minimize-the-total-price-of-the-trips/solution/lei-si-da-jia-jie-she-iii-pythonjavacgo-4k3wq/?????
2646. 最小化旅行的價格總和
解法1——暴力dfs每條路徑
核心思路是遍歷每條路徑，修改 price 數(shù)組，然后將問題轉(zhuǎn)換成 337. 打家劫舍 III 。
class Solution {
List<Integer>[] g;
int[] price, cnt;
int end;
public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList());
for (int[] edge: edges) {
int x = edge[0], y = edge[1];
g[x].add(y);
g[y].add(x);
}
this.price = price;
cnt = new int[n]; // 記錄每個節(jié)點在路徑中出現(xiàn)的次數(shù)
for (int[] trip: trips) {
end = trip[1];
op(trip[0], -1); // 用dfs找到這個trip路徑上的點
}
int[] p = dfs(0, -1);
return Math.min(p[0], p[1]);
}
public boolean op(int x, int father) {
if (x == end) { // 找到了end
++cnt[x];
return true;
}
for (int y: g[x]) {
if (y != father && op(y, x)) {
++cnt[x];
return true;
}
}
return false; // 沒找到
}
// 返回值 ：[不減半，減半]
public int[] dfs(int x, int father) {
int notHalve = price[x] * cnt[x], halve = notHalve / 2;
for (int y: g[x]) {
if (y != father) {
int[] p = dfs(y, x);
notHalve += Math.min(p[0], p[1]); // 當(dāng)前不減半，那前面的節(jié)點隨意
halve += p[0]; // 當(dāng)前減半，那前面的節(jié)點只能不減半
}
}
return new int[]{notHalve, halve};
}
}
解法2——Tarjan 離線 LCA + 樹上差分
TODO
https://leetcode.cn/problems/minimize-the-total-price-of-the-trips/solution/lei-si-da-jia-jie-she-iii-pythonjavacgo-4k3wq/
補充題目：2467. 樹上最大得分和路徑???
2467. 樹上最大得分和路徑
這道題目更多的是練習(xí)樹的 dfs 技巧，與 dp 關(guān)系不大。
使用兩個 dfs ，
第一個 dfs 用于計算 bob 達(dá)到各點的時間，為計算 alice 路徑上的價值做準(zhǔn)備。
第二個 dfs 用于枚舉 alice 到達(dá)各個葉子節(jié)點的路徑，在達(dá)到葉子節(jié)點時更新答案。文章來源：http://www.zghlxwxcb.cn/news/detail-520922.html
class Solution {
List<Integer>[] g;
int[] bobTime, amount;
int ans = Integer.MIN_VALUE;
public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
int n = edges.length + 1;
g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList());
for (int[] edge: edges) {
int x = edge[0], y =edge[1];
g[x].add(y);
g[y].add(x);
}
g[0].add(-1); // 常用技巧，給0節(jié)點加一個父節(jié)點-1，可以少寫多余判斷
this.amount = amount;
bobTime = new int[n]; // 記錄bob到達(dá)該節(jié)點的時間
Arrays.fill(bobTime, Integer.MAX_VALUE); // 初始化為bob都到不了
dfsBob(bob, 0, -1);
dfsAlice(0, 0, -1, 0);
return ans;
}
// 當(dāng)前節(jié)點、當(dāng)前節(jié)點的時間、當(dāng)前節(jié)點的父節(jié)點
public boolean dfsBob(int x, int time, int father) {
// 只有到達(dá)了目的地才設(shè)置時間
if (x == 0) {
bobTime[x] = time;
return true;
}
for (int y: g[x]) {
if (y != father && dfsBob(y, time + 1, x)) {
bobTime[x] = time;
return true;
}
}
return false;
}
public void dfsAlice(int x, int time, int father, int score) {
// 計算當(dāng)前節(jié)點的值
int curVal = 0;
if (time == bobTime[x]) curVal = amount[x] / 2;
else if (time < bobTime[x]) curVal = amount[x]; // a早到
// 到達(dá)了葉子節(jié)點，使用該條路徑的值更新答案
if (g[x].size() == 1) {
ans = Math.max(ans, score + curVal);
return;
}
// dfs過程
for (int y: g[x]) {
if (y != father) {
dfsAlice(y, time + 1, x, score + curVal);
}
}
return;
}
}
注意：！
在 bob dfs 的過程中，不是經(jīng)過的所有節(jié)點都需要被設(shè)置時間的，而是只有達(dá)到了 0 節(jié)點路徑上的節(jié)點才需要被設(shè)置時間。
因此一個常用技巧是讓 dfs 返回一個 boolean 值來記錄是否達(dá)到了 target 。文章來源地址http://www.zghlxwxcb.cn/news/detail-520922.html
到了這里，關(guān)于【算法】樹形DP ② 打家劫舍Ⅲ（樹上最大獨立集）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
