设计网站推荐免费,牛推网络,快速进入网站,吉林网站建设设计本文涉及的基础知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 动态规划#xff0c;日后完成。
题目
有 n 堆石头排成一排#xff0c;第 i 堆中有 stones[i] 块石头。 每次 移动 需要将 连续的 k 堆石头合并为一堆#xff0c;而…本文涉及的基础知识点
C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 动态规划日后完成。
题目
有 n 堆石头排成一排第 i 堆中有 stones[i] 块石头。 每次 移动 需要将 连续的 k 堆石头合并为一堆而这次移动的成本为这 k 堆中石头的总数。 返回把所有石头合并成一堆的最低成本。如果无法合并成一堆返回 -1 。 示例 1 输入stones [3,2,4,1], K 2 输出20 解释 从 [3, 2, 4, 1] 开始。 合并 [3, 2]成本为 5剩下 [5, 4, 1]。 合并 [4, 1]成本为 5剩下 [5, 5]。 合并 [5, 5]成本为 10剩下 [10]。 总成本 20这是可能的最小值。 示例 2 输入stones [3,2,4,1], K 3 输出-1 解释任何合并操作后都会剩下 2 堆我们无法再进行合并。所以这项任务是不可能完成的。. 示例 3 输入stones [3,5,1,2,6], K 3 输出25 解释 从 [3, 5, 1, 2, 6] 开始。 合并 [5, 1, 2]成本为 8剩下 [3, 8, 6]。 合并 [3, 8, 6]成本为 17剩下 [17]。 总成本 25这是可能的最小值。 提示 n stones.length 1 n 30 1 stones[i] 100 2 k 30
分析
dp[begin][end]记录stones[begin,end)合并后的最小得分。时间复杂度O(nnn)状态数:n*n转移状态时间复杂度O(n)。
状态转移
假定stones[begin,end)是由stone[begin,m)和stone[m,end)合并成的m取值范围(begin,end)。stone[begin,m)简称左堆stone[m,end)简称右堆。
左右两堆剩余石头数之和小于kdp[begin][end] dp[begin][m]dp[m][end]左右两堆剩余石头数之和等于于kdp[begin][end] dp[begin][m]dp[m][end]vPreSum[begin][end],石头发生了合并左右两堆剩余石头数之和大于于k抛弃
左右两堆剩余石头数之和大于于k
抛弃左右两堆剩余石头数之和大于于k也可以找到最优解。
最后一轮只有k个石头故不会超过k倒数第二轮只有2k-1个石头假定其范围是[i0,j0)倒数第二轮是[i1,j1) 那么[i0,j0)会合并这时两堆石头恰好是k故不会超过k……
剩余石头数
每次合并后石头数减少k-1。所有石头数减1再对k-1求求余再加1。 注意先判断石头数是否是1不是直接返回-1。
代码
核心代码
class Solution {
public:int mergeStones(vectorint stones, int K) {m_c stones.size();if (1 ! RemainLen(m_c,K)){return -1;}vectorint vPreSum { 0 };for (const auto n : stones){vPreSum.emplace_back(n vPreSum.back());}vectorvectorint dp(m_c,vectorint(m_c1));//dp[i][j] 表示合并stones[i,j)的最小成本for (int len 2; len m_c; len){for (int begin 0; begin len m_c; begin){const int end begin len;int iMin INT_MAX;for (int m begin 1; m end; m){const int iAdd RemainLen(m - begin, K) RemainLen(end - m, K);if (iAdd K){continue;}int cur dp[begin][m] dp[m][end];iMin min(iMin, cur);}if (1 RemainLen(len, K)){iMin vPreSum[end] - vPreSum[begin];}dp[begin][end] iMin;} }return dp.front().back();}int RemainLen(int len, int k){return 1(len - 1) % (k - 1);}int m_c;
};测试代码
templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){assert(v1[i] v2[i]);}
}templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}int main()
{vectorint stones { 3,5,1,2,6 };int k 3;int res Solution().mergeStones(stones, k);Assert(25, res);stones { 3,2,4,1 };k 2;res Solution().mergeStones(stones, k);Assert(20, res); stones { 1,2,3,4,5,6,7 };k 3;res Solution().mergeStones(stones, k);Assert(49, res);stones { 1,2,3,4,5,6,7 };k 4;res Solution().mergeStones(stones, k);Assert(38, res);stones { 1,2,3,4,5,6,7,8,9 };k 5;res Solution().mergeStones(stones, k);Assert(60, res);//stones { 9, 8, 7, 6, 5, 4, 3, 2, 1 };k 2;res Solution().mergeStones(stones, k);Assert(135, res);stones { 9,8,7,6,5,4,3,2,1 };k 3;res Solution().mergeStones(stones, k);Assert(87, res);stones { 10,9,8,7,6,5,4,3,2,1 };k 4;res Solution().mergeStones(stones, k);Assert(91, res);//stones { 5,8,7,6,5,12,13,14,4,3,2,1,2 };k 4;res Solution().mergeStones(stones, k);Assert(155, res);stones { 2,8,7,6,5,12,13,14,4,3,2,1,2 };k 5;res Solution().mergeStones(stones, k);Assert(119, res);//CConsole::Out(res);
}旧版代码 templateclass Tvoid MinSelf(T* seft, const T other){*seft min(*seft, other);}
class Solution {public:int mergeStones(vectorint stones, int k) {m_k k;m_c stones.size();m_dp.assign(m_c 1, vectorvectorint(m_c, vectorint(k 1, 1000 * 1000 * 100)));vectorint vPreSum(1);for (const auto stone : stones){vPreSum.push_back(vPreSum.back() stone);}for (int pos 0; pos 1 - 1 m_c; pos){m_dp[1][pos][1] 0;}for (int len 2; len m_c; len){for (int pos 0; poslen m_c; pos){//int iEnd pos len - 1;for (int iHeapNum 2; iHeapNum k; iHeapNum){for (int iPreLen 1; iPreLen len; iPreLen k - 1){MinSelf(m_dp[len][pos][iHeapNum], m_dp[iPreLen][pos][1] m_dp[len - iPreLen][pos iPreLen][iHeapNum - 1]);}}m_dp[len][pos][1] m_dp[len][pos][k] vPreSum[pos len] - vPreSum[pos];} } return (m_dp[m_c][0][1] 1000 * 1000 * 100) ? -1 : m_dp[m_c][0][1];}int m_k;int m_c;vectorvectorvectorint m_dp;};旧版代码2 templateclass Tvoid MinSelf(T* seft, const T other){*seft min(*seft, other);}class Solution {public:int mergeStones(vectorint stones, int k) {m_k k;m_c stones.size();m_dp.assign(m_c 1, vectorint(m_c, ( 1000 * 1000 * 100)));if ((m_c-1) % (k - 1) ! 0){return -1;}vectorint vPreSum(1);for (const auto stone : stones){vPreSum.push_back(vPreSum.back() stone);}for (int pos 0; pos 1 - 1 m_c; pos){m_dp[1][pos] 0;}for (int len 2; len m_c; len){for (int pos 0; poslen m_c; pos){for (int iPreLen 1; iPreLen len; iPreLen k - 1){MinSelf(m_dp[len][pos], m_dp[iPreLen][pos] m_dp[len - iPreLen][pos iPreLen]);}if ((len-1) % (k - 1) 0){m_dp[len][pos] vPreSum[pos len] - vPreSum[pos];}} } return (m_dp[m_c][0] 1000 * 1000 * 100) ? -1 : m_dp[m_c][0];}int m_k;int m_c;vectorvectorint m_dp;};旧版代码三
class Solution { public: int mergeStones(vector stones, int k) { m_c stones.size(); if (0 ! (m_c - 1) % (k-1)) { return -1; } vector vPreSum(1); for (const auto n : stones) { vPreSum.emplace_back(vPreSum.back() n); } vectorvector vLenBegin(m_c 1, vector(m_c)); for (int len k; len m_c; len) { for (int begin 0; begin len - 1 m_c; begin) { int iMaxPreScore INT_MAX; for (int lLen 1; lLen len; lLen (k - 1)) { int rLen len - lLen; iMaxPreScore min(iMaxPreScore, vLenBegin[lLen][begin] vLenBegin[rLen][begin lLen]); } if (0 (len - 1) % (k - 1)) { iMaxPreScore vPreSum[begin len] - vPreSum[begin]; } vLenBegin[len][begin] iMaxPreScore ; } } return vLenBegin.back().front(); } int m_c; };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 C17 或者 操作系统win10 开发环境
VS2022 C17
