C++で要素を削除するための所定のルールを使用して配列の可能な最小サイズを見つけます

この問題では、n個の数値と整数値kの配列が与えられます。私たちのタスクは、要素を削除するための所定のルールを使用して、配列の可能な最小サイズを見つけることです。

問題の説明 −配列内の要素の数を最小限に抑える必要があります。次の削除操作を使用すると、一度に削除できる要素の数は3になります。3つの要素が2つの指定された条件を満たす場合、削除が可能です。

条件1 −3つの要素が隣接している必要があります。>

条件2 − 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の場合、1つの削除操作が可能です。

ソリューションアプローチ

この問題は、1回の削除操作が実行された後に表示される可能性のある間接的な削除操作が存在する可能性があるため、解決するのが少し難しいです。たとえば、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