作者推荐
本文涉及知识点
LeetCode312 戳气球
有 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
动态规划
nums前后各加一个1，设增加两个1后，nums的长度为m_c。则问题转化为nums[0,m_c-1] ，消除掉nums(0,m_c-1),不消除nums[0]和nums[m_c-1]的最大得分。我们用函数f(0,m_c-1)表示。我们枚举最后消除的元素k，则f(i,j)=f(i,k)+nums[i]*nums[k]*nums[j]+f(k,j)。
k的取值范围(i,j)
共有mn种状态，故空间复杂度是O(nm)，每种状态的转移时间复杂度是O(1)，故时间复杂度是O(nm)。m和n是t和s的长度。
| 动态规划的状态表示 | dp[i][j]等于f(i,j) |
| 动态规划的转移方程 | f(i,j)=f(i,k)+nums[i]*nums[k]*nums[j]+f(k,j) |
| 动态规划的初始状态 | 全部0 |
| 动态规划的填表顺序 | len = j-i+1。len < 3 ，dp[i][j]=0，无需处理。第一层循环len从3到m_c，第二层循环i从小到大。由短到长处理子字符串,确保动态规划的无后效性 |
| 动态规划的返回值 | dp[0].back() |
空间复杂度: 子数组的起点和终点，各n种可能。故空间复杂度:O(nn)。
时间复杂度: 状态nn种，每种状态的转移时间复杂度O(n)，故总时间复杂度O(n3)。
代码
核心代码
class Solution { public: int maxCoins(vector<int>& nums) { nums.insert(nums.begin(), 1); nums.emplace_back(1); m_c = nums.size(); vector<vector<int>> dp(m_c, vector<int>(m_c)); for (int len = 3; len <= m_c; len++) { int j; for (int i = 0; (j = i+len-1) < m_c; i++) { for (int k = i + 1; k < j; k++) { dp[i][j] = max(dp[i][j], dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]); } } } return dp[0].back(); } int m_c; };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } 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]); } } int main() { vector<int> nums; { Solution sln; nums = { 3, 1, 5, 8 }; auto res = sln.maxCoins(nums); Assert(167, res); } { Solution sln; nums = { 1,5 }; auto res = sln.maxCoins(nums); Assert(10, res); } }
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年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<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; };
