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(2ⁿ)降为O(n)。
状态数为n³，故空间复杂度为O(n³)，时间复杂度为:O(n⁴)。许多状态不可能同时存在，实际时间复杂度低得多。

动态规划分析

动态规划的转移方程表示：
所有盒子都会被消除，所以boxes[r]也是，枚举boxes[r]被消除的可能：
情况一：boxes[r]被消除时，r的下标最小（最左边)。转移方程为:(k+1)*(k+1) + dp[l][r-1][0]
情况二：boxes[r]被消除时，有元素r1在它的左边和它一起消除。r1的下标比r小，且boxs[r]==boxs[r1]。转移方程为：dp[l][r1][k+1] + dp[r1+1][r-1][0]

动态规划的初始状态：
全部为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;
};