# C++前缀和算法：合并石头的最低成本原理、源码及测试用例（二）

### 旧版代码

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;
};

### 旧版代码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;
};

### 旧版代码三

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);
}
vector<vector> 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;
};

## 扩展阅读

#### 视频课程

https://edu.csdn.net/course/detail/38771

https://edu.csdn.net/lecturer/6176

#### 相关下载

 鄙人想对大家说的话 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 墨家名称的来源：有所得以墨记之。 如果程序是一条龙，那算法就是他的是睛

#### 测试环境

VS2022 C++17

|
21小时前
|

c++算法学习笔记 (5)前缀和+差分
c++算法学习笔记 (5)前缀和+差分
8 1
|
3天前
|

【算法基础】基础算法（二）--（高精度、前缀和、差分）（下）
【算法基础】基础算法（二）--（高精度、前缀和、差分）（下）
12 0
|
3天前
|

【算法基础】基础算法（二）--（高精度、前缀和、差分）（上）
【算法基础】基础算法（二）--（高精度、前缀和、差分）（上）
10 0
|
8天前
|
NoSQL 算法 Java
【redis源码学习】持久化机制，java程序员面试算法宝典pdf
【redis源码学习】持久化机制，java程序员面试算法宝典pdf
21 0
|
9天前
|

[设计模式Java实现附plantuml源码~行为型]定义算法的框架——模板方法模式
[设计模式Java实现附plantuml源码~行为型]定义算法的框架——模板方法模式
18 0
|
9天前
|

winform车牌识别源码（纯算法）

19 0
|
9天前
|

【优选算法专栏】专题四：前缀和（二）
【优选算法专栏】专题四：前缀和（二）
23 1
|
9天前
|

【优选算法专栏】专题四：前缀和（一）
【优选算法专栏】专题四：前缀和（一）
26 0
|
9天前
|

4 0
|
9天前
|

28 5