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

2024-01-13 19:40
文章标签 算法 动态 规划 c++ 搜索 记忆 移除 盒子 546

本文主要是介绍【动态规划】【记忆化搜索】C++算法：546移除盒子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】458:可怜的小猪

本文涉及知识点

动态规划 记忆化搜索

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]

i4f[i4-1][0]+(k+1) ^2l ,i4,0
i3 i4f[i3][1]+g(i3,i4)l ,i4,0 -->l,i3,1
i2 i4f[i2][1]+g(i2,i4)l ,i4,0 ->l,i2,1
i1 i4f[i1][1]+g(i1,i4)l ,i4,0 >l,i1,1
i1 i2 i4f[i1][2]+g(i1,i2)+g{i2,i4)l ,i4,0 --> l,i2,1 -> l,i1->2
i1 i3 i4f[i1][2]+g(i1,i3)+g{i3,i4)l ,i4,0 --> l,i3,1 -> l,i1->2
i2 i3 i4f[i2][2]+g(i2,i3)+g{i3,i4)l ,i4,0 --> l,i3,1 -> l,i2->2
i1 i2 i3 i4f[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++**实现。

这篇关于【动态规划】【记忆化搜索】C++算法：546移除盒子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/602568。

相关文章

C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2