数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找具有给定元素移除规则的数组的最小可能大小
在这个问题中，我们给定一个包含 n 个数字的数组和一个整数 k。我们的任务是查找具有给定元素移除规则的数组的最小可能大小。
问题描述 - 我们需要最小化数组中的元素数量。通过使用以下删除操作，每次可以移除的元素数量为 3。如果三个元素满足两个给定条件，则可以进行移除，
条件 1 - 三个元素应该是相邻的。>
条件 2 - 两个相邻元素之间的差值为 k，即 arr[i + 1] = arr[i] + k 且 arr[i+2] = arr[i+1] + k。
让我们举个例子来理解这个问题，
输入
{4, 6, 8, 4, 1, 5 }, k = 2输出
3
解释
可以进行一次删除操作，索引为 0、1、2。
解决方案方法
这个问题有点棘手，因为可能存在间接的删除操作，这些操作可以在执行一次删除操作后才能看到。例如，我们删除索引 5、6、7 处的元素。在此删除操作之后，新数组可能包含元素 3、4、5，现在它们满足删除条件。此类具有重叠子问题的问题可以使用动态规划方法解决。为此，我们将维护一个 DP[] 矩阵来存储子问题的结果，以便以后在需要时访问它们，这称为记忆化。
程序说明我们解决方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int DP[MAX][MAX];
int calcMinSize(int arr[], int start, int end, int k){
if (DP[start][end] != -1)
return DP[start][end];
if ( (end-start + 1) < 3)
return end-start +1;
int minSize = 1 + calcMinSize(arr, start+1, end, k);
for (int i = start+1; i<=end-1; i++){
for (int j = i+1; j <= end; j++ ){
if (arr[i] == (arr[start] + k) && arr[j] == (arr[start] +
2*k) && calcMinSize(arr, start+1, i-1, k) == 0 && calcMinSize(arr, i+1, j- 1, k) == 0) {
minSize = min(minSize, calcMinSize(arr, j+1, end, k));
}
}
}
return (DP[start][end] = minSize);
}
int main() {
int arr[] = {4, 6, 8, 4, 1, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
memset(DP, -1, sizeof(DP));
cout<<"The minimum possible size of the array after removal is "<<calcMinSize(arr, 0, n-1, k);
return 0;
}输出
The minimum possible size of the array after removal is 3
更新于： 2021 年 3 月 12 日
494 次查看
广告