本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
一张桌子上总共有 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
分析
时间复杂度
三层循环，第一层循环，枚举各栈；第二层循环，枚举已经取走的硬币数；第三层循环，枚举本栈取走的硬币。令m=sum(piles[i].length)，第一层和第三层循环的总复杂度是O(m)。第二次循环的复杂度是O(k)，故复杂度为O(km)。
变量解释
| pre | pre[i]的值是选取i枚硬币的最大值 |
| i | 之前的栈总共选取了i枚硬币 |
| j | 本次选取了j枚硬币 |
代码
核心代码
class Solution { public: int maxValueOfCoins(vector<vector>& piles, int k) { vector pre = { 0 };//pre[i]的值是选取i枚硬币的最大值 for (const auto& v : piles ) { const int iNum = min((int)v.size() + (int)pre.size(),k+1); vector dp(iNum); for (int i = 0; i < pre.size(); i++) { //当前栈选取j枚硬币 int iSum = 0; for (int j = 0; j <= v.size(); j++) { const int iNewNum = i + j; if (iNewNum > k) { continue; } dp[iNewNum] = max(dp[iNewNum], pre[i]+iSum); if (j < v.size()) { iSum += v[j]; } } } pre.swap(dp); } return pre.back(); } };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { Solution slu; vector<vector> piles; int k = 0; int res;
piles = { {1,100,3},{7,8,9} }; k = 2; res = slu.maxValueOfCoins(piles, k); Assert(101, res); piles = { {100},{100},{100},{100},{100},{100},{1,1,1,1,1,1,700} }; k = 7; res = slu.maxValueOfCoins(piles, k); Assert(101, res); //CConsole::Out(res);
}
2023年2月旧代码
class Solution { public: int maxValueOfCoins(vector<vector>& piles, int k) { vector pre(1); for (const auto& v : piles) { const int iSize = min(k + 1,int( pre.size()+ v.size())); vector dp = pre; dp.resize(iSize); int iTotal = 0; for (int i = 0; i < v.size(); i++) { iTotal += v[i]; for (int j = 0; j < pre.size() ; j++) { const int iNewIndex = j + i + 1; if (iNewIndex > k) { break; } dp[iNewIndex] = max(dp[iNewIndex], pre[j] + iTotal); } } pre.swap(dp); } return pre[k]; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 鄙人想对大家说的话
|
|-|
|闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。|
| 墨家名称的来源：有所得以墨记之。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
