代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
一张桌子上总共有 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] <= 105
1 <= k <= sum(piles[i].length) <= 2000
方法一:动态规划
对每个栈求前缀和 $s$,$s_i$ 视为一个体积为 $i$ 且价值为 $s_i$ 的物品。
问题转化为求从 $n$ 个物品组中取物品体积为 $k$,且每组最多取一个物品时的最大价值和。
定义 $dp[i][j]$ 表示从前 $i$ 个组中取体积之和为 $j$ 的物品时的最大价值和。
枚举第 $i$ 组所有物品,设当前物品体积为 $w$,价值为 $v$,则有 $f[i][j]=max(f[i][j],f[i-1][j-w]+v)$。
class Solution:
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
presum = [list(accumulate(p, initial=0)) for p in piles]
n = len(piles)
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i, s in enumerate(presum, 1):
for j in range(k + 1):
for idx, v in enumerate(s):
if j >= idx:
dp[i][j] = max(dp[i][j], dp[i - 1][j - idx] + v)
return dp[-1][-1]
class Solution:
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
presum = [list(accumulate(p, initial=0)) for p in piles]
dp = [0] * (k + 1)
for s in presum:
for j in range(k, -1, -1):
for idx, v in enumerate(s):
if j >= idx:
dp[j] = max(dp[j], dp[j - idx] + v)
return dp[-1]
class Solution {
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
int n = piles.size();
List<int[]> presum = new ArrayList<>();
for (List<Integer> p : piles) {
int m = p.size();
int[] s = new int[m + 1];
for (int i = 0; i < m; ++i) {
s[i + 1] = s[i] + p.get(i);
}
presum.add(s);
}
int[] dp = new int[k + 1];
for (int[] s : presum) {
for (int j = k; j >= 0; --j) {
for (int idx = 0; idx < s.length; ++idx) {
if (j >= idx) {
dp[j] = Math.max(dp[j], dp[j - idx] + s[idx]);
}
}
}
}
return dp[k];
}
}
class Solution {
public:
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
vector<vector<int>> presum;
for (auto& p : piles) {
int m = p.size();
vector<int> s(m + 1);
for (int i = 0; i < m; ++i) s[i + 1] = s[i] + p[i];
presum.push_back(s);
}
vector<int> dp(k + 1);
for (auto& s : presum) {
for (int j = k; ~j; --j) {
for (int idx = 0; idx < s.size(); ++idx) {
if (j >= idx) dp[j] = max(dp[j], dp[j - idx] + s[idx]);
}
}
}
return dp[k];
}
};
func maxValueOfCoins(piles [][]int, k int) int {
var presum [][]int
for _, p := range piles {
m := len(p)
s := make([]int, m+1)
for i, v := range p {
s[i+1] = s[i] + v
}
presum = append(presum, s)
}
dp := make([]int, k+1)
for _, s := range presum {
for j := k; j >= 0; j-- {
for idx, v := range s {
if j >= idx {
dp[j] = max(dp[j], dp[j-idx]+v)
}
}
}
}
return dp[k]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。