题目
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 315 + 358 + 138 + 181 = 167
示例 2：
输入：nums = [1,5]
输出：10
参数范围
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
2023年一月版本
class Solution {
public:
int maxCoins(vector& nums) {
int iMax = 0;
m_c = nums.size();
vector<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年5月版
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<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;
};相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
鄙人想对大家说的话 |
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
墨家名称的来源：有所得以墨记之。 |
如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
