在这个问题中，我们得到了一个由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<<"移除后阵列的最小可能大小为 "<<calcMinSize(arr, 0, n-1, k);
return 0;
}输出结果移除后阵列的最小可能大小为 3