【动态规划-分组背包】【hard】力扣2218. 从栈中取出 K 个硬币的最大面值和

一张桌子上总共有 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
解释：
如果我们所有硬币都从最后一个栈中取，可以得到最大面值和。

动态规划

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        vector<int> f(k+1);
        int num_n = 0;
        for(auto& pile : piles){
            int n = pile.size();
            for(int i = 1; i < n; i++){
                pile[i] += pile[i-1];
            }
            
            int num_n = min(num_n+n, k);
            for(int j = num_n; j > 0; j--){
                for(int w = 0; w < min(n,j); w++){
                    f[j] = max(f[j],f[j-w-1] + pile[w]); 
                }
            }
        }
        return f[k];
    }
};

时间复杂度：O(ks)。将外层循环与最内层循环合并，即每个栈的大小之和，记作 s，算上中间这层的循环，时间复杂度为 O(ks)。
空间复杂度：O(k)。

首先定义一个动态数组f，f[j]的含义是：当使用j个硬币所能达到的最大面值和。
我们遍历每一个栈的硬币，然后计算出前缀和，使pile[i]的含义变为前i+1个硬币的面值和。
然后定义一个整型num_n，他是用来判断j要从哪里开始向下循环，每当遍历一个栈的时候，num_n就会加上这个栈的硬币数n，然后保证不会超过k。

然后j就从num_n开始向下循环到j>0，然后第三重循环w的含义是目前遍历的栈选取w+1个硬币，然后这时候更新f[j]，他会比较如果选取了这个栈的前w+1个硬币，那么有没有可能会出现比之前更大的情况。

最后f[k]的含义就是取出k个硬币时候的最大面值和，返回即可。