千问 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] (j1)子节点的状态变为 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. 构建邻接表表示树ListInteger[] 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 0int[][] memo new int[n][14];for (int[] row : memo) {Arrays.fill(row, -1); // -1 表示未计算过}// 3. 从根节点 0 开始 DFS初始父节点为 -1初始减半次数为 0return dfs(0, 0, -1, memo, graph, coins, k);}private int dfs(int i, int j, int father, int[][] memo, ListInteger[] 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// 子节点的减半次数依然保持为 jint res1 currentCoin - k;// 策略2使用方式2收集 (coins[i] j) / 2// 子节点的减半次数变为 j 1int 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没必要继续深入递归计算 res2if (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 很大时比如超过 13coins[i] j 已经等于 0 了。此时继续递归 j1 没有意义可以直接剪枝避免不必要的计算。