-
C++前缀和算法：合并石头的最低成本原理、源码及测试用例
本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
动态规划，日后完成。LeetCode 1000合并石头的最低成本
有 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)简称右堆。
左右两堆剩余石头数之和小于k dp[begin][end] = dp[begin][m]+dp[m][end] 左右两堆剩余石头数之和等于于k dp[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(vector<int>& stones, int K) { m_c = stones.size(); if (1 != RemainLen(m_c,K)) { return -1; } vector<int> vPreSum = { 0 }; for (const auto& n : stones) { vPreSum.emplace_back(n + vPreSum.back()); } vector<vector<int>> dp(m_c,vector<int>(m_c+1));//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; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
测试代码
template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector<int> 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); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
旧版代码
template<class T> void MinSelf(T* seft, const T& other) { *seft = min(*seft, other); } class Solution { public: int mergeStones(vector<int>& stones, int k) { m_k = k; m_c = stones.size(); m_dp.assign(m_c + 1, vector<vector<int>>(m_c, vector<int>(k + 1, 1000 * 1000 * 100))); vector<int> 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; pos+len <= 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; vector<vector<vector<int>>> m_dp; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
旧版代码2
template<class T> void MinSelf(T* seft, const T& other) { *seft = min(*seft, other); } class Solution { public: int mergeStones(vector<int>& stones, int k) { m_k = k; m_c = stones.size(); m_dp.assign(m_c + 1, vector<int>(m_c, ( 1000 * 1000 * 100))); if ((m_c-1) % (k - 1) != 0) { return -1; } vector<int> 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; pos+len <= 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; vector<vector<int>> m_dp; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
旧版代码三
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);
}
vectorvLenBegin(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 C++17
或者 操作系统：win10 开发环境：VS2022 C++17
-
相关阅读:
KY34 Is It A Tree?
「Python」面向对象封装案例3——士兵突击（需求分析、代码演练）
redis 源码分析：Jedis 哨兵模式连接原理
基于端智能的播放QoE优化
机器学习——推荐系统和强化学习
物理气相沉积半导体设备 PVD DSP/ARM+FPGA控制器设计
VR-Platform 国产神器
JavaWeb之HTTP、Tomcat、Servlet
（五）正点原子STM32MP135移植——烧录
TimeSformer:Is Space-Time attention all you need for video understanding?
- 原文地址：https://blog.csdn.net/he_zhidan/article/details/133958246