文章

[LeetCode] 每日一题 2218. 从栈中取出 K 个硬币的最大面值和

题目链接

https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles

题目描述

一张桌子上总共有 n 个硬币  。每个栈有 正整数 个带面值的硬币。

每一次操作中,你可以从任意一个栈的 顶部 取出 1 个硬币,从栈中移除它,并放入你的钱包里。

给你一个列表 piles ,其中 piles[i] 是一个整数数组,分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k ,请你返回在 恰好 进行 k 次操作的前提下,你钱包里硬币面值之和 最大为多少 。

示例输入

示例 1

输入:piles = [[1,100,3],[7,8,9]], k = 2

输出:101

解释:
上图展示了几种选择 k 个硬币的不同方法。
我们可以得到的最大面值为 101 。

示例 2

输入:piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7

输出:706

解释:
如果我们所有硬币都从最后一个栈中取,可以得到最大面值和。

提示

  • n == piles.length

  • 1 <= n <= 1000

  • 1 <= piles[i][j] <= 10^5

  • 1 <= k <= sum(piles[i].length) <= 2000

解题思路

本题是一个典型的 分组背包问题,可以通过 记忆化搜索动态规划 来解决。我们可以定义一个递归函数 dfs(i, j),表示从前 i 组物品中选择硬币,且总共选择的硬币数量不超过 j 的情况下,能够得到的最大硬币价值

  • 每次选择时,我们可以选择从当前栈中取一定数量的硬币,考虑从栈的顶部开始取一个一个硬币,直到满足 k 次取硬币的约束

  • 如果当前栈中选择的硬币总价值为 v,且总重量为 w,那么问题就转化为:从前 i-1 组中选择硬币,且剩余容量为 j-w,得到的最大价值为 dfs(i-1, j-w)。然后将 v 加入,得到当前栈中的最大价值

通过记忆化搜索,我们避免了重复计算相同的子问题,从而提升了效率

代码实现

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int numPiles = piles.size();
        int[][] memo = new int[numPiles][k + 1];
        return dfs(numPiles - 1, k, piles, memo);
    }

    // dfs(i, j) 表示从 piles[0] 到 piles[i] 中,选体积之和至多为 j 的物品时,物品价值之和的最大值
    private int dfs(int pileIndex, int remainingCapacity, List<List<Integer>> piles, int[][] memo) {
        if (pileIndex < 0) {
            return 0;
        }
        // 如果已经计算过,直接返回结果
        if (memo[pileIndex][remainingCapacity] != 0) {
            return memo[pileIndex][remainingCapacity];
        }
        // 不选当前物品组的情况
        int maxValue = dfs(pileIndex - 1, remainingCapacity, piles, memo);
        // 当前物品组的总价值
        int currentSum = 0;
        // 当前物品组的物品数量
        int numItemsInCurrentPile = piles.get(pileIndex).size();
        for (int i = 0; i < Math.min(remainingCapacity, numItemsInCurrentPile); i++) {
            currentSum += piles.get(pileIndex).get(i);
            maxValue = Math.max(maxValue, dfs(pileIndex - 1, remainingCapacity - i - 1, piles, memo) + currentSum);
        }
        // 将计算的最大值记入记忆化数组
        return memo[pileIndex][remainingCapacity] = maxValue;
    }
}

复杂度分析

  • 时间复杂度

    • 假设 n 是栈的数量,k 是可以操作的次数,m 是每个栈的最大硬币数

    • 对于每个栈,我们需要计算所有可能的选取硬币的方式(从 0 到该栈所有硬币的数量),对于每个选取方案,我们进行一次递归调用

    • 由于每个状态 dfs(i, j) 都会被缓存一次,因此时间复杂度为 O(n * k * m),其中 n 是栈的数量,k 是操作次数,m 是栈中最大硬币数

  • 空间复杂度

    • 由于使用了一个二维 memo 数组来存储每个子问题的结果,因此空间复杂度为 O(n * k)

总结

今天的题目难度对我来说确实比较大,主要是因为涉及到的分组背包问题需要较强的状态转移和记忆化搜索技巧。虽然数值范围被限制了,我依然觉得用深度搜索来硬解出来是比较合适的选择。通过这道题,我对转化成 分组背包问题记忆化搜索递推空间优化 等知识点的掌握还不够深入,尤其是在复杂度控制和背包问题的递推转化方面,我需要加强对这些技巧的理解和应用。通过今天的练习,我也更加意识到解题过程中思路的重要性和灵活性,今后会更加注重这些技巧的巩固与提升

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

License:  CC BY 4.0