旧版代码
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; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
