it is title
  • 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

2023年一月版

class Solution {
public:
int maxCoins(vector& nums) {
int iMax = 0;
m_c = nums.size();
vector dp;
dp.assign(m_c+1, vector(m_c));
for (int len = 1; len <= m_c; len++)
{
for (int c = 0; c + len - 1 < m_c; c++)
{
//计算dp[len][c]
//m是最后的气球,这样保证可以拆分两个子项
for (int m = c; m <= c + len - 1; m++)
{
int iSource = GetSource(nums, m,c-1,c+len);
if (m > c)
{
iSource += dp[m - c][c];
}
if (m < c + len - 1)
{
iSource += dp[c + len - 1 - m][m + 1];
}
dp[len][c] = max(dp[len][c], iSource);
}
}
}
return dp[m_c][0];
}
int GetSource(const vector& nums,int c,int iLeft,int iRight)
{
int iScource = nums[c];
if (iLeft >= 0)
{
iScource *= nums[iLeft];
}
if (iRight < m_c)
{
iScource *= nums[iRight];
}
return iScource;
}
int m_c;
};

2023年6月版

class Solution {
public:
int maxCoins(vector& nums) {
nums.insert(nums.begin(), 1);
nums.emplace_back(1);
m_c = nums.size();
//dp[len][iBegin]表示iBegin开始长度为len的区间,消除得剩余首尾2个元素获得的积分
vector dp(m_c + 1, vector(m_c, 0));
for (int len = 3; len <= m_c; len++)
{
for (int begin = 0; begin + len - 1 < m_c; begin++)
{
const int end = begin + len - 1;
for (int mid = begin + 1; mid < end; mid++)
{
const int leftLen = mid - begin + 1;
const int rightLen = len - leftLen + 1;
const int iNew = dp[leftLen][begin] + nums[begin] * nums[mid] * nums[end] + dp[rightLen][mid];
dp[len][begin] = max(dp[len][begin], iNew);
}
}
}
return dp.back()[0];
}
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

class="table-box">
我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

data-report-view="{"mod":"1585297308_001","spm":"1001.2101.3001.6548","dest":"https://blog.csdn.net/he_zhidan/article/details/135415198","extend1":"pc","ab":"new"}">> id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"> class="blog_extension blog_extension_type5" id="blog_extension"> class="extension_official" data-report-click="{"spm":"1001.2101.3001.6471"}" data-report-view="{"spm":"1001.2101.3001.6471"}"> class="blog_extension_card_left"> class="blog_extension_card_cont"> 群中有博文配套源码 class="blog_extension_card_cont_r"> QQ群名片
注:本文转载自blog.csdn.net的昊虹AI笔记的文章"https://blog.csdn.net/wenhao_ir/article/details/134435333"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。

评论记录:

未查询到任何数据!