2218 从栈中取出 K 个硬币的最大面值和

题目链接

2218. 从栈中取出 K 个硬币的最大面值和

分析

对每一个栈求前缀和 $sum[]$，即可将其转化为分组背包问题（将每个栈中取前 $1,2,3,\cdots, n$ 个分别看作一个物品，体积分别为 $1,2,3,\cdots, n$，价值为 $sum[1], sum[2], sum[3], \cdots, sum[n]$

令 $dp[i][j]$ 为从前 $i$ 个栈取 $j$ 个硬币时能取的最大金额，当前选择的物品由 $w$ 个金币构成，价值为 $v$

那么状态转移方程就是 $dp[i][j]=\max(dp[i-1][j], dp[i - 1][j - w] + v)$

在实现时反向进行遍历，可以去掉上述转移方程的第一维

代码实现

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        vector<int> dp(k + 1, 0);
        for (auto& p : piles) {
            int n = p.size();
            partial_sum(p.begin(), p.end(), p.begin());
            for(int i = k; i; --i) {
                for(int j = 0; j < min(n, i); ++j) {
                    dp[i] = max(dp[i], dp[i - j - 1] + p[j]);
                }
            }
        }
        return dp[k];
    }
};

复杂度分析

• 时间复杂度：$O(Nk)$，$N$ 为所有栈的长度之和
• 空间复杂度：$O(k)$