LeetCode546. 移除盒子
给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。
返回 你能获得的最大积分和 。
示例 1：
输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (33=9 分)
----> [1, 3, 3, 3, 1] (11=1 分)
----> [1, 1] (33=9 分)
----> [] (22=4 分)
示例 2：
输入：boxes = [1,1,1]
输出：9
示例 3：
输入：boxes = [1]
输出：1
提示：
1 <= boxes.length <= 100
1 <= boxes[i] <= 100
动态规划
动态规划的状态表示：
dp[l][r][k]表示消除以下子序列获得的最大得分。
boxes[0,l)已经消除或不会对消除此子序列有影响。
boxes[l,r]全部没有消除。
boxes(r,n)除k个boxes[r]外，全部消除。
思路
假定boxs[i1]、boxs[i2]、boxs[i3]、boxes[i4]相等，且不存在其它等于boxs[i4]的盒子。消除i4时有如下可能。
为了方便，用g(l,r)代替 dp[l+1][r-1][0] f(r,k)代替dp[0][r][k]
| i4 | f[i4-1][0]+(k+1) ^2 | l ,i4,0 |
| i3 i4 | f[i3][1]+g(i3,i4) | l ,i4,0 -->l,i3,1 |
| i2 i4 | f[i2][1]+g(i2,i4) | l ,i4,0 ->l,i2,1 |
| i1 i4 | f[i1][1]+g(i1,i4) | l ,i4,0 >l,i1,1 |
| i1 i2 i4 | f[i1][2]+g(i1,i2)+g{i2,i4) | l ,i4,0 --> l,i2,1 -> l,i1->2 |
| i1 i3 i4 | f[i1][2]+g(i1,i3)+g{i3,i4) | l ,i4,0 --> l,i3,1 -> l,i1->2 |
| i2 i3 i4 | f[i2][2]+g(i2,i3)+g{i3,i4) | l ,i4,0 --> l,i3,1 -> l,i2->2 |
| i1 i2 i3 i4 | f[i1][3]+g(i1,i2)+g{i2,i3)++g{i3,i4) | l ,i4,0 --> l,i3,1 ->l,i2->2–>l,i1,3 |
我们以i1 i2 i4 为例：
f[i4][0]可能等于 f[i2][1] + g[i2,i4]
f[i2][1]可能等于f[i1][2] + g[i1+i2]
==> f[i4][0] 可能等于 f[i1]i2] + g[i1][i2] + g[i2][i4]
** 结论** 枚举消除时，不用枚举所有一同消除的下标，只需要枚举前一个下标。这意味着转移方程的时间复杂度从O(2n)降为O(n)。
状态数为n3，故空间复杂度为O(n3)，时间复杂度为:O(n4)。许多状态不可能同时存在，实际时间复杂度低得多。
动态规划分析
动态规划的转移方程表示：
所有盒子都会被消除，所以boxes[r]也是，枚举boxes[r]被消除的可能：
情况一：boxes[r]被消除时，r的下标最小（最左边)。转移方程为:(k+1)*(k+1) + dp[l][r-1][0]
情况二：boxes[r]被消除时，i的小标比r小，如果有多个i取最大值。转移方程为：dp[i+1][r+1][0] + dp[l][i][k+1]
动态规划的初始状态：
全部为0，表示未计算。
动态规划的填表顺序：
计算dp[0][n-1][0]需要的状态。
动态规划的返回值：
dp[0][n-1][0]
枚举了不可能的情况
比如： {1,2,1,1} 由于boxs[2]和boxs[3]之间没有其它数字，所以它们一定同时被消除。
假定boxs[i1]boxs[i2]=x，且i1+1i2。
假定一：i1和i2被两次消除。 不失一般性，假定i1先被消除。包括i1共k1个x被消除，包括i2共k2个x被消除。
假定二：假定i1和i2之间没数据。除不消i1外，其它操作及顺序和假定一相同，直到消除i2。则时消除k0+k1+k2个x。 k1个boxs[i1]左边可以有k0个可以一并消除。在假定1中，这个k0x无论是一次消除还是多次消除都小于等于k0k0。除了这些x外,其它完全一样。假定一<=k0k0+k1k2+k2k2 假定二：(k0+k1+k2)^2。显然假定一 <= 假定二
这k0个x可能在假定一中和更左边的结合，那假定二可能等待这些都消除了，再消除i2。
结论： 假定一不存在，但它一定不优于假定二，假定二存在，所以多枚举了假定一，不会带来错误结果。
代码
核心代码
class Solution { public: int removeBoxes(vector<int>& boxes) { m_c = boxes.size(); m_boxes = boxes; for (int i = 0; i < m_c; i++) { m_dp[i].assign(m_c, vector<int>(m_c)); } return Cal(0,m_c-1,0); } int Cal(const int& l, const int& r, const int& k) { if (l > r) { return 0; } if (0 != m_dp[l][r][k]) { return m_dp[l][r][k]; } m_dp[l][r][k] = Cal(l, r - 1, 0) + (k + 1) * (k + 1); for (int i = l; i < r; i++) { if (m_boxes[i] == m_boxes[r]) { m_dp[l][r][k] = max(m_dp[l][r][k], Cal(l, i, k + 1)+ Cal(i+1,r-1,0)); } } return m_dp[l][r][k]; } int m_c; vector<int> m_boxes; vector < vector<int>> m_dp[100]; };
测试用例
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> boxes; { Solution sln; boxes = { 1, 2, 2, 1, 1, 1, 2, 1 }; auto res = sln.removeBoxes(boxes); Assert(30, res); } { Solution sln; boxes = { 1, 3, 2, 2, 2, 3, 4, 3, 1 }; auto res = sln.removeBoxes(boxes); Assert(23, res); } { Solution sln; boxes = { 1,1,1 }; auto res = sln.removeBoxes(boxes); Assert(9, res); } { Solution sln; boxes = { 1 }; auto res = sln.removeBoxes(boxes); Assert(1, res); } { Solution sln; boxes = { 1,2,1 }; auto res = sln.removeBoxes(boxes); Assert(5, res); } { Solution sln; boxes = { 1,2,2,1,1,1,2,1,1,2,1,2,1,1,2,2,1,1,2,2,1,1,1,2,2,2,2,1,2,1,1,2,2,1,2,1,2,2,2,2,2,1,2,1,2,2,1,1,1,2,2,1,2,1,2,2,1,2,1,1,1,2,2,2,2,2,1,2,2,2,2,2,1,1,1,1,1,2,2,2,2,2,1,1,1,1,2,2,1,1,1,1,1,1,1,2,1,2,2,1 }; auto res = sln.removeBoxes(boxes); Assert(2758, res); } }
2023年1月代码
class Solution { public: int removeBoxes(vector& boxes) { memset(m_dp, 0, sizeof(m_dp)); return Cal(boxes,0, boxes.size() - 1, 0); } int Cal(const vector& boxes,int l, int r, int k) { if (l > r) { return 0; } if (0 != m_dp[l][r][k]) { return m_dp[l][r][k]; } int iSum = Cal(boxes,l, r - 1, 0) + (k + 1)*(k + 1); for (int i = l; i < r; i++) { if (boxes[i] != boxes[r]) { continue; } iSum = max(iSum, Cal(boxes, l, i, k + 1) + Cal(boxes, i + 1, r - 1, 0)); } m_dp[l][r][k] = iSum; return m_dp[l][r][k]; } int m_dp[100][100][100] ; };
2023年6月代码
class Solution { public: int removeBoxes(vector& boxes) { m_c = boxes.size(); memset(m_aLRNum, -1, sizeof(m_aLRNum)); return remove(boxes,0, m_c - 1, 0); } int remove(const vector& boxes,const int left, const int right, int k) { if (right < left) { return 0; } int& iRet = m_aLRNum[left][right][k]; if (iRet >= 0) { return iRet; } iRet = (1 + k)*(1 + k) + remove(boxes,left, right - 1, 0); int tmp = right-1; //[1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 2, 2, 2, 1],可以先消除中间，只保留两个1 while (tmp >= left) { while ((tmp >= left) && (boxes[tmp] != boxes[right])) { tmp–; } if (tmp < left) { return iRet; } iRet = max(iRet, remove(boxes, tmp + 1, right - 1, 0) + remove(boxes, left, tmp, k + 1)); tmp–; } return iRet; } int m_c; int m_aLRNum[100][100][100];//m_aLRNum[l][r][k] 消除nums的[l.r]及和nums[r]相等的k个数 };
2023年8月代码
class Solution { public: int removeBoxes(vector& boxes) { m_boxes = boxes; //dp[l][r][k]表示 boxes[l] 到boxes[r] 是最后消除的，消除时后面有k同颜色的数 memset(m_dp, 0, sizeof(m_dp)); return Cal(0, boxes.size() - 1, 0); } int Cal(int left, int r, int k) { if (r < left) { return 0; } int& iRet = m_dp[left][r][k]; if (0 != iRet) { return iRet; } iRet = Cal(left, r - 1, 0) + (k + 1) * (k + 1);//直接消除 for (int i = r - 1; i >= left; i–) { if (m_boxes[i] != m_boxes[r]) { continue; } iRet = max(iRet, Cal(left, i, k + 1) + Cal(i + 1, r - 1, 0)); } return iRet; } int m_dp[100][100][100]; vector m_boxes; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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**
如无特殊说明，本算法用**C++**实现。
