文章

[LeetCode] 每日一题 2920. 收集所有金币可获得的最大积分

题目链接

https://leetcode.cn/problems/maximum-points-after-collecting-coins-from-all-nodes

题目描述

有一棵由 n 个节点组成的无向树,以 0  为根节点,节点编号从 0n - 1 。给你一个长度为 n - 1 的二维 整数 数组 edges ,其中 edges[i] = [ai, bi] 表示在树上的节点 aibi 之间存在一条边。另给你一个下标从 0 开始、长度为 n 的数组 coins 和一个整数 k ,其中 coins[i] 表示节点 i 处的金币数量。

从根节点开始,你必须收集所有金币。要想收集节点上的金币,必须先收集该节点的祖先节点上的金币。

节点 i 上的金币可以用下述方法之一进行收集:

  • 收集所有金币,得到共计 coins[i] - k 点积分。如果 coins[i] - k 是负数,你将会失去 abs(coins[i] - k) 点积分。

  • 收集所有金币,得到共计 floor(coins[i] / 2) 点积分。如果采用这种方法,节点 i 子树中所有节点 j 的金币数 coins[j] 将会减少至 floor(coins[j] / 2)

返回收集 所有 树节点的金币之后可以获得的最大积分。

示例输入

示例 1

输入:edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
输出:11                        
解释:
使用第一种方法收集节点 0 上的所有金币。总积分 = 10 - 5 = 5 。
使用第一种方法收集节点 1 上的所有金币。总积分 = 5 + (10 - 5) = 10 。
使用第二种方法收集节点 2 上的所有金币。所以节点 3 上的金币将会变为 floor(3 / 2) = 1 ,总积分 = 10 + floor(3 / 2) = 11 。
使用第二种方法收集节点 3 上的所有金币。总积分 =  11 + floor(1 / 2) = 11.
可以证明收集所有节点上的金币能获得的最大积分是 11 。

示例 2

输入:edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
输出:16
解释:
使用第一种方法收集所有节点上的金币,因此,总积分 = (8 - 0) + (4 - 0) + (4 - 0) = 16 。

提示

  • n == coins.length

  • 2 <= n <= 10^5

  • 0 <= coins[i] <= 10^4

  • edges.length == n - 1

  • 0 <= edges[i][0], edges[i][1] < n

  • 0 <= k <= 10^4

解题思路

本题要求在树上收集金币,可以通过两种方式收集:一种是直接收集金币并扣除一个固定的积分,另一种是通过右移运算收集金币,但会影响子树中所有节点的金币数量。任务是求从根节点开始收集所有金币后能够获得的最大积分。

我们可以使用记忆化搜索来求解这个问题。具体做法是,递归地遍历树的每个节点,对于每个节点,有两种选择:不右移或者右移。通过状态记录来避免重复计算,保证高效性。记忆化搜索的状态由节点和当前右移的次数组成,避免了不必要的递归计算。

参考了灵茶山艾府大佬的思路:https://leetcode.cn/problems/maximum-points-after-collecting-coins-from-all-nodes/solutions/2503152/shu-xing-dp-ji-yi-hua-sou-suo-by-endless-phzx

代码实现

class Solution {
    public int maximumPoints(int[][] edges, int[] coins, int k) {
        int n = coins.length;
        List<Integer>[] graph = new ArrayList[n];
        Arrays.setAll(graph, i -> new ArrayList<>());
        // 构建无向图
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            graph[u].add(v);
            graph[v].add(u);
        }
        int[][] memo = new int[n][14];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(0, 0, -1, memo, graph, coins, k);
    }

    private int dfs(int node, int shiftCount, int parent, int[][] memo, List<Integer>[] graph, int[] coins, int k) {
        // 如果该状态已经计算过,直接返回结果
        if (memo[node][shiftCount] != -1) {
            return memo[node][shiftCount];
        }
        // 当前节点不右移的积分
        int noShiftPoints = (coins[node] >> shiftCount) - k;
        // 当前节点右移一次的积分
        int shiftPoints = coins[node] >> (shiftCount + 1);
        for (int neighbor : graph[node]) {
            if (neighbor == parent) continue;
            // 递归计算不右移的积分
            noShiftPoints += dfs(neighbor, shiftCount, node, memo, graph, coins, k);
            // 递归计算右移的积分,前提是右移次数不超过限制
            if (shiftCount < 13) {
                shiftPoints += dfs(neighbor, shiftCount + 1, node, memo, graph, coins, k);
            }
        }
        return memo[node][shiftCount] = Math.max(noShiftPoints, shiftPoints);
    }
}

复杂度分析

  • 时间复杂度:O(n * logU),其中 n 是节点数,U 是 coins 数组中金币的最大值。每个节点最多执行 logU 次右移操作,因此最多有 n * logU 次状态计算

  • 空间复杂度:O(n * logU),需要一个二维数组 memo 来存储每个节点在不同右移次数下的计算结果,最多有 n * logU 个状态

总结

这道题通过树形结构和记忆化搜索结合的方式,解决了如何选择最优的方式收集金币的问题。通过判断当前节点选择右移还是不右移,并利用记忆化搜索避免重复计算,保证了高效性。

问题的关键在于如何合理地进行状态管理,并通过递归遍历树的每个节点,求出最大积分。通过优化的代码,我们可以确保即使在大数据量下也能高效计算出正确答案。

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0