এই সমস্যায়, আমাদেরকে 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
