【动态规划】【记忆化搜索】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++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/317110.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

[C++]多态

[C++]多态

目录 C多态&#xff1a;&#xff1a; 多态的概念 多态的定义及实现 多态的构成条件 虚函数 虚函数的重写 虚函数重写的特例 C11 override和final 重载、重写重定义的对比 抽象类 概念 接口继承和实现继承 多态的原理 虚函数表 多态的原理 动态绑定和静态绑定 单继承和…
阅读更多...
智能分析网关V4：搭建智慧幼儿园视频AI智能监管方案

智能分析网关V4：搭建智慧幼儿园视频AI智能监管方案

一、背景需求 随着科技的日新月异&#xff0c;智慧化监管在幼儿园管理领域的应用已成为不可逆转的趋势。在传统的幼儿园管理模式中&#xff0c;校园安全管理往往依赖于人工查看监控&#xff0c;难以及时发现安全隐患。智慧幼儿园监管解决方案通过引入物联网、大数据、人工智能…
阅读更多...
C# IOC 容器实战：KeyedService和生命周期

C# IOC 容器实战：KeyedService和生命周期

文章目录 前言KeyedServiceKey缺少Key值覆盖 KeyedService.AnyKey生命周期测试代码 总结 前言 我之前写过一篇Ioc容器的使用&#xff0c;用的是微软的IOC容器。这次我们再去深入了解一下IOC 和控制反转 .NET Core 依赖注入 Microsoft.Extensions.DependencyInjection ASP.NET …
阅读更多...
josef约瑟 中间继电器 HJDZ-E440额定电压:AC220V 卡轨安装

josef约瑟 中间继电器 HJDZ-E440额定电压:AC220V 卡轨安装

HJDZ-静态中间继电器 系列型号&#xff1a; HJDZ-A200静态中间继电器&#xff1b;HJDZ-A110静态中间继电器&#xff1b; HJDZ-A002静态中间继电器&#xff1b;HJDZ-A004静态中间继电器&#xff1b; HJDZ-E112静态中间继电器&#xff1b;HJDZ-E112L静态中间继电器&#xff1…
阅读更多...
数据结构入门到入土——栈(Stack)和队列(Queue)

数据结构入门到入土——栈(Stack)和队列(Queue)

目录 一&#xff0c;栈&#xff08;Stack&#xff09; 1.1 概念 1.2 栈的使用 1.3 栈的模拟实现 1.4 栈的应用场景 1.5 栈&#xff0c;虚拟机栈&#xff0c;栈帧有什么区别&#xff1f; 二&#xff0c;队列&#xff08;Queue&#xff09; 2.1 概念 2.2 队列的使用 2.3 …
阅读更多...
luceda ipkiss教程 55：画螺旋型布拉格光栅

luceda ipkiss教程 55：画螺旋型布拉格光栅

案例分享, 画螺旋型布拉格光栅: 所有代码如下&#xff1a; from si_fab import all as pdk import ipkiss3.all as i3 from picazzo3.wg.spirals import FixedLengthSpiralRoundedgrating_size 0.7 grating_wg_width 1.2 wg_width 0.5 pitch 1.4 reference i3.LayoutCel…
阅读更多...
【HuggingFace Transformer库学习笔记】基础组件学习：Datasets

【HuggingFace Transformer库学习笔记】基础组件学习：Datasets

基础组件——Datasets datasets基本使用 导入包 from datasets import *加载数据 datasets load_dataset("madao33/new-title-chinese") datasetsDatasetDict({train: Dataset({features: [title, content],num_rows: 5850})validation: Dataset({features: [titl…
阅读更多...
【Web】NSSCTF Round#16 Basic个人wp(全)

【Web】NSSCTF Round#16 Basic个人wp(全)

出题友好&#xff0c;适合手生复健。 目录 ①RCE但是没有完全RCE ②了解过PHP特性吗 ①RCE但是没有完全RCE 上来就是一段md5八股 (string)就是不让用数组了&#xff0c;然后强比较需要md5碰撞 ?md5_1%4d%c9%68%ff%0e%e3%5c%20%95%72%d4%77%7b%72%15%87%d3%6f%a7%b2%1b%dc…
阅读更多...
KVM Vcpu概述

KVM Vcpu概述

KVM Vcpu概述 Intel VTSMP系统CPU过载使用CPU模型CPU绑定和亲和性CPU优化 Intel VT Intel的硬件虚拟化技术大致分为3类&#xff1a; 1、VT-x技术&#xff1a;是指Intel处理器中的一些虚拟化技术支持&#xff0c;包括CPU中最基础的VMX技术&#xff0c;也包括内存虚拟化的硬件支…
阅读更多...
【LangChain学习之旅】—（7） 调用模型：使用OpenAI API还是微调开源Llama2/ChatGLM？

【LangChain学习之旅】—（7） 调用模型：使用OpenAI API还是微调开源Llama2/ChatGLM？

【LangChain学习之旅】—&#xff08;7&#xff09; 调用模型&#xff1a;使用OpenAI API还是微调开源Llama2/ChatGLM&#xff1f; 大语言模型发展史预训练 微调的模式用 HuggingFace 跑开源模型申请使用 Meta 的 Llama2 模型通过 HuggingFace 调用 LlamaLangChain 和 Hugging…
阅读更多...
PHP代码审计基础知识

PHP代码审计基础知识

前言 本文章主要是PHP代码审计的一些基础知识&#xff0c;包括函数的用法&#xff0c;漏洞点&#xff0c;偏向基础部分&#xff0c;个人能力有限&#xff0c;部分可能会出现错误或者遗漏&#xff0c;读者可自行补充。 代码执行 代码执行是代码审计当中较为严重的漏洞&…
阅读更多...
关于LwRB环形缓冲区开源库的纯C++版本支持原子操作

关于LwRB环形缓冲区开源库的纯C++版本支持原子操作

1、LwRB环形缓冲区开源库&#xff1a; GitHub - MaJerle/lwrb: Lightweight generic ring buffer manager libraryLightweight generic ring buffer manager library. Contribute to MaJerle/lwrb development by creating an account on GitHub.https://github.com/MaJerle/l…
阅读更多...
【Linux】Linux基础之权限

【Linux】Linux基础之权限

目录 一、Linux中的用户1.1 用户之间的身份切换1.2 指令提权 二、权限管理2.1 文件权限2.2 权限操作2.3 chown和chgrp 三、文件类型四、目录文件的权限操作五、权限掩码六、粘滞位 一、Linux中的用户 Linux中主要有两种用户&#xff1a; root&#xff0c;超级用户非root&…
阅读更多...
AI智能创作软件，颠覆你的写作体验

AI智能创作软件，颠覆你的写作体验

你是否想过&#xff0c;有一天&#xff0c;文字创作不再受限于人的思维和表达能力&#xff1f;AI智能文章创作就是这样一个神奇的存在。它运用先进的自然语言处理技术&#xff0c;通过对大量数据的深度学习&#xff0c;根据需要自动生成文章。你只需输入关键词或主题&#xff0…
阅读更多...
Vue3-完成任意组件之间的传值

Vue3-完成任意组件之间的传值

一、props&#xff08;只限于父子之间&#xff0c;不嫌麻烦可以不断传&#xff09; 父给子传值&#xff0c;子接收defineProps 父给子传事件&#xff0c;子接收defineProps&#xff0c;并触发事件的时候传值&#xff0c;然后父通过事件的回调函数拿到子传的值 二、mitt&#…
阅读更多...
R语言将list转变为dataframe（常用）

R语言将list转变为dataframe（常用）

在R语言使用中常常遇到list文件需要转变为dataframe格式文件处理。这是需要写循环来进行转换。IOBR查看其收录的相关基因集(自备)_iobr_deg-CSDN博客 示例文件 list文件&#xff1a; 循环转换为dataframe data <- signature_tme dat <- as.data.frame(t(sapply(data, …
阅读更多...
【AI的未来 - AI Agent系列】【MetaGPT】0. 你的第一个MetaGPT程序

【AI的未来 - AI Agent系列】【MetaGPT】0. 你的第一个MetaGPT程序

《MetaGPT智能体开发入门》开课&#xff0c;跟着课程&#xff0c;学习MetaGPT智能体开发。 0. 安装MetaGPT 请确保你的系统已安装Python 3.9。你可以通过以下命令进行检查&#xff1a; python3 --version下面是具体的安装命令&#xff1a; 安装命令 pip install metagpt如…
阅读更多...
完美解决报错Please verify that the package.json has a valid “main“ entry处理方法

完美解决报错Please verify that the package.json has a valid “main“ entry处理方法

出现下图中的错误 &#xff0c;说明缺少main入口 解决方法&#xff1a; 1.删除 node_modules 和 package-lock.json这两个文件 2.命令行输入npm i 会重新下载包 3.重新执行检查没有报错
阅读更多...
Centos安装RocketMQ之双主双从模式（同步双写方式）

Centos安装RocketMQ之双主双从模式（同步双写方式）

目录 前言 一、总体架构 二、环境准备 1、文件准备 2、服务器换环境 3、防火墙配置 4、创建消息存储路径 三、配置文件修改 1、master1配置修改 2、slave2配置修改 3、master2配置修改 4、slave1配置修改 四、启动脚本修改 五、启动服务 1、启动NameServe集群 ​编…
阅读更多...
阿里云高性能云服务器_云主机_云服务器详解

阿里云高性能云服务器_云主机_云服务器详解

阿里云高性能云服务器60%单实例最大性能提升&#xff0c;35Gbps内网带宽&#xff0c;网络增强&通用型云服务器、本地SSD型云服务器、大数据型云服务器、GPU异构型云服务器&#xff0c;阿里云百科aliyunbaike.com分享阿里云高性能云服务器&#xff1a; 阿里云高性能云服务器…
阅读更多...
最新文章

Copyright @ 2022~2023