千问 LeetCode 2920. 收集所有金币可获得的最大积分 Java实现
这是一道非常经典的树形动态规划（Tree DP）结合记忆化搜索的题目。
💡 核心解题思路
1. 题目分析：
* 这是一棵无向树，我们需要从根节点（0）出发收集所有金币。
* 每个节点有两种收集方式：
* 方式1：获得 coins[i] - k 积分。
* 方式2：获得 coins[i] / 2 积分，但代价是当前节点子树中所有节点的金币都会减半。
2. 关键洞察（状态压缩）：
* 题目中金币的最大值 coins[i] 不超过 10000。
* 一个数连续除以 2（右移），最多只需要 14 次就会变成 0（因为 2^{14} = 16384 > 10000）。
* 因此，我们不需要真正去修改子树中每个节点的金币数值。我们只需要用一个状态 j 来记录从根节点到当前节点的路径上，一共执行了多少次“方式2”的操作。
3. 状态定义：
* 定义 dfs(i, j, father) 表示：当前在节点 i，其祖先节点（不包括自己）一共执行了 j 次“方式2”操作，且父节点为 father 时，以 i 为根的子树能获得的最大积分。
4. 状态转移：
* 当前节点 i 的实际金币数为 coins[i] >> j（即 coins[i] / 2^j）。
* 选择方式1：当前获得 (coins[i] >> j) - k，子节点的状态依然是 j。
* 选择方式2：当前获得 (coins[i] >> j) >> 1（即 coins[i] >> (j+1)），子节点的状态变为 j + 1。
* 取两者的最大值即可。
💻 Java 代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public int maximumPoints(int[][] edges, int[] coins, int k) {
int n = coins.length;
// 1. 构建邻接表表示树
List<Integer>[] graph = new ArrayList[n];
Arrays.setAll(graph, i -> new ArrayList<>());
for (int[] edge : edges) {
int x = edge[0];
int y = edge[1];
graph[x].add(y);
graph[y].add(x);
}
// 2. 初始化记忆化数组 memo[i][j]
// 表示节点 i 在祖先进行了 j 次减半操作下的最大积分
// j 最大取 14 即可，因为 10000 >> 14 = 0
int[][] memo = new int[n][14];
for (int[] row : memo) {
Arrays.fill(row, -1); // -1 表示未计算过
}
// 3. 从根节点 0 开始 DFS，初始父节点为 -1，初始减半次数为 0
return dfs(0, 0, -1, memo, graph, coins, k);
}
private int dfs(int i, int j, int father, int[][] memo, List<Integer>[] graph, int[] coins, int k) {
// 如果该状态已经计算过，直接返回
if (memo[i][j] != -1) {
return memo[i][j];
}
// 当前节点 i 在经过 j 次减半后的实际金币数
int currentCoin = coins[i] >> j;
// 策略1：使用方式1收集 (coins[i] >> j) - k
// 子节点的减半次数依然保持为 j
int res1 = currentCoin - k;
// 策略2：使用方式2收集 (coins[i] >> j) / 2
// 子节点的减半次数变为 j + 1
int res2 = currentCoin >> 1;
// 遍历所有子节点（排除父节点）
for (int child : graph[i]) {
if (child == father) {
continue;
}
// 累加策略1下，子树的收益
res1 += dfs(child, j, i, memo, graph, coins, k);
// 累加策略2下，子树的收益
// 剪枝：如果 j >= 13，说明再右移一次金币肯定为0，没必要继续深入递归计算 res2
if (j < 13) {
res2 += dfs(child, j + 1, i, memo, graph, coins, k);
}
}
// 记录并返回最大值
memo[i][j] = Math.max(res1, res2);
return memo[i][j];
}
}
📊 复杂度分析
* 时间复杂度：O(N)。其中 N 是节点数量。虽然看起来有很多状态，但由于金币数最多减半 14 次就会变成 0，状态数被限制在 N times 14 以内。每个状态只会被计算一次，因此整体接近线性时间复杂度。
* 空间复杂度：O(N)。主要用于存储邻接表 graph 和记忆化数组 memo，以及递归调用的栈空间。
⚠️ 易错点提示
* 避免死循环：树是无向图转换来的，DFS 时一定要传入 father 参数，防止在父子节点之间来回遍历。
* 右移边界：当 j 很大时（比如超过 13），coins[i] >> j 已经等于 0 了。此时继续递归 j+1 没有意义，可以直接剪枝，避免不必要的计算。