golang 解法, 执行用时: 44 ms, 内存消耗: 4.3 MB, 提交时间: 2023-09-25 11:18:23

func maxValueOfCoins(piles [][]int, k int) int {
	f := make([]int, k+1)
	sumN := 0
	for _, pile := range piles {
		n := len(pile)
		for i := 1; i < n; i++ {
			pile[i] += pile[i-1] // pile 前缀和
		}
		sumN = min(sumN+n, k) // 优化：j 从前 i 个栈的大小之和开始枚举（不超过 k）
		for j := sumN; j > 0; j-- {
			for w, v := range pile[:min(n, j)] {
				f[j] = max(f[j], f[j-w-1]+v) // w 从 0 开始，物品体积为 w+1
			}
		}
	}
	return f[k]
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

cpp 解法, 执行用时: 196 ms, 内存消耗: 11.2 MB, 提交时间: 2023-09-25 11:18:09

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>> &piles, int k) {
        vector<int> f(k + 1);
        int sumN = 0;
        for (auto &pile: piles) {
            int n = pile.size();
            for (int i = 1; i < n; ++i)
                pile[i] += pile[i - 1]; // pile 前缀和
            sumN = min(sumN + n, k); // 优化：j 从前 i 个栈的大小之和开始枚举（不超过 k）
            for (int j = sumN; j; --j)
                for (int w = 0; w < min(n, j); ++w)
                    f[j] = max(f[j], f[j - w - 1] + pile[w]); // w 从 0 开始，物品体积为 w+1
        }
        return f[k];
    }
};

java 解法, 执行用时: 140 ms, 内存消耗: 42 MB, 提交时间: 2023-09-25 11:17:55

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        var f = new int[k + 1];
        var sumN = 0;
        for (var pile : piles) {
            var n = pile.size();
            for (var i = 1; i < n; ++i)
                pile.set(i, pile.get(i) + pile.get(i - 1)); // pile 前缀和
            sumN = Math.min(sumN + n, k); // 优化：j 从前 i 个栈的大小之和开始枚举（不超过 k）
            for (var j = sumN; j > 0; --j)
                for (var w = 0; w < Math.min(n, j); ++w)
                    f[j] = Math.max(f[j], f[j - w - 1] + pile.get(w)); // w 从 0 开始，物品体积为 w+1
        }
        return f[k];
    }
}

python3 解法, 执行用时: 2980 ms, 内存消耗: 16.3 MB, 提交时间: 2023-09-25 11:17:41

'''
问题转化成求从 n 个物品组里面取物品体积和为 k 的物品，且每组至多取一个物品时的物品价值最大和，即分组背包模型。

定义 f[i][j] 表示从前 i 个组取体积之和为 j 的物品时，物品价值之和的最大值。
枚举第 i 个组的所有物品，设当前物品体积为 w，价值为 v，则有 f[i][j]=max⁡(f[i][j],f[i−1][j−w]+v)
答案为 f[n][k]。
'''
class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        f = [0] * (k + 1)
        sum_n = 0
        for pile in piles:
            n = len(pile)
            for i in range(1, n):
                pile[i] += pile[i - 1]  # pile 前缀和
            sum_n = min(sum_n + n, k)  # 优化：j 从前 i 个栈的大小之和开始枚举（不超过 k）
            for j in range(sum_n, 0, -1):
                f[j] = max(f[j], max(f[j - w - 1] + pile[w] for w in range(min(n, j))))  # w 从 0 开始，物品体积为 w+1
        return f[k]