【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++**实现。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/523510.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!