【动态规划】【记忆化搜索】C++算法：546移除盒子

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

记忆化搜索

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]

我们以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]被消除时，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;

};