当前位置: 首页 > article >正文

【C++动态规划】2547. 拆分数组的最小代价|2019

本文涉及知识点

C++动态规划 化分型

LeetCode2547. 拆分数组的最小代价

给你一个整数数组 nums 和一个整数 k 。
将数组拆分成一些非空子数组。拆分的 代价 是每个子数组中的 重要性 之和。
令 trimmed(subarray) 作为子数组的一个特征,其中所有仅出现一次的数字将会被移除。
例如,trimmed([3,1,2,4,3,4]) = [3,4,3,4] 。
子数组的 重要性 定义为 k + trimmed(subarray).length 。
例如,如果一个子数组是 [1,2,3,3,3,4,4] ,trimmed([1,2,3,3,3,4,4]) = [3,3,3,4,4] 。这个子数组的重要性就是 k + 5 。
找出并返回拆分 nums 的所有可行方案中的最小代价。
子数组 是数组的一个连续 非空 元素序列。
示例 1:
输入:nums = [1,2,1,2,1,3,3], k = 2
输出:8
解释:将 nums 拆分成两个子数组:[1,2], [1,2,1,3,3]
[1,2] 的重要性是 2 + (0) = 2 。
[1,2,1,3,3] 的重要性是 2 + (2 + 2) = 6 。
拆分的代价是 2 + 6 = 8 ,可以证明这是所有可行的拆分方案中的最小代价。
示例 2:
输入:nums = [1,2,1,2,1], k = 2
输出:6
解释:将 nums 拆分成两个子数组:[1,2], [1,2,1] 。
[1,2] 的重要性是 2 + (0) = 2 。
[1,2,1] 的重要性是 2 + (2) = 4 。
拆分的代价是 2 + 4 = 6 ,可以证明这是所有可行的拆分方案中的最小代价。
示例 3:
输入:nums = [1,2,1,2,1], k = 5
输出:10
解释:将 nums 拆分成一个子数组:[1,2,1,2,1].
[1,2,1,2,1] 的重要性是 5 + (3 + 2) = 10 。
拆分的代价是 10 ,可以证明这是所有可行的拆分方案中的最小代价。
提示:
1 <= nums.length <= 1000
0 <= nums[i] < nums.length
1 <= k <= 109

动态规划+ 划分型

动态规划的状态表现

mat[i][j]记录 子数组nums[i…j]的扣除单个元素的数量。mCnt记录nums[i…j-1]各元素的数量。x = mCnt[nums[j]],如果x为0,则mat[i][j]=mat[i][j-1];如果x==1,则mat[i][j] =mat[i][j-1]+2; 其它mat[i][j] = mat[i][j-1]+1;
dp[i]记录处理了前i个元素的最小和。

动态规划的填报顺序

枚举前置状态,i =0 to N-1 j = i to N-1。

动态规划的转移方程

MinSelf(dp[j+1],dp[i]+k+mat[i][j])

动态规划的初始值

dp[0]=0,其它全是INT_MAX/2

动态规划的返回值

dp.back()

代码

class Solution {
		public:
			int minCost(vector<int>& nums, int k) {
				const int N = nums.size();
				vector<vector<int>> mat(N, vector<int>(N));
				for (int i = 0; i < N; i++) {
					unordered_map<int, int> mCnt;
					mCnt[nums[i]]++;
					for (int j = i+1; j < N; j++) {
						int& t = mCnt[nums[j]];
						int add = 1;
						if (0 == t) { add = 0; }
						if (1 == t) { add = 2; }
						t++;
						mat[i][j] = mat[i][j - 1] + add;
					}
				}
				vector<long long> dp(N + 1, LLONG_MAX / 2);
				dp[0] = 0;
				for (int i = 0; i < N; i++) {
					for (int j = i; j < N; j++) {
						dp[j + 1] = min(dp[j + 1], dp[i] + k + mat[i][j]);
					}
				}
				return dp.back();
			}
		};

单元测试

vector<int> nums;
		int k;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1,2,1,2,1,3,3 }, k = 2;
			auto res = Solution().minCost(nums, k);
			AssertEx(8, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,2,1,2,1 }, k = 2;
			auto res = Solution().minCost(nums, k);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 1,2,1,2,1 }, k = 5;
			auto res = Solution().minCost(nums, k);
			AssertEx(10, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

原文地址:https://blog.csdn.net/he_zhidan/article/details/143590857
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/523510.html

相关文章:

  • 手机ROM是什么
  • 在 Android 中实现 H5 文件下载功能:跨版本文件存储机制解析
  • Flask使用JWT认证
  • 2.2 反向传播:神经网络如何“学习“?
  • VS2022中.Net Api + Vue 从创建到发布到IIS
  • A Unified Model for Multi-class Anomaly Detection
  • 【论文投稿-第八届智能制造与自动化学术会议(IMA 2025)】HTML, CSS, JavaScript:三者的联系与区别
  • SOME/IP--协议英文原文讲解2
  • Python3 【函数】水平考试:精选试题和答案
  • MySQL数据导入与导出
  • MFC的绘制问题
  • p4:使用pytorch实现猴痘病识别
  • MySQL常用数据类型和表的操作
  • 【25美赛A题-F题全题目解析】2025年美国大学生数学建模竞赛(MCM/ICM)解题思路|完整代码论文集合
  • Linux 内核学习(4) --- devfreq 动态调频框架
  • 01学习预热篇(D6_正式踏入JVM深入学习前的铺垫)
  • An Attention Free Transformer论文参考文献
  • java 判断Date是上午还是下午
  • 基础IO(2)
  • 试用ChatGPT开发一个大语言模型聊天App
  • 51单片机开发:定时器中断
  • FaceFusion
  • Java set 方法和static 方法的用途
  • ELF动态信息
  • 读书笔记:《华为突围ERP封锁全纪实》
  • wordpress代码结构解析