ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে বলা হয় সংখ্যা। এখন আমরা একটি অপারেশন বিবেচনা করি যেখানে আমরা কিছু সাবলিস্ট মুছে ফেলি যা একটি প্যালিনড্রোম। আমাদের প্রয়োজন ন্যূনতম সংখ্যক অপারেশন খুঁজে বের করতে হবে যাতে তালিকাটি খালি থাকে।
সুতরাং, ইনপুট যদি nums =[6, 2, 4, 4, 2, 10, 6] এর মত হয়, তাহলে আউটপুট হবে 2, যেমন আমরা প্রথমে সাবলিস্ট [2, 4, 4, 2] সরিয়ে দিতে পারি তারপর তালিকাটি হল [6, 10, 6] এর মতো এটিও একটি প্যালিনড্রোম, তাই তালিকাটি খালি করতে এটি সরিয়ে ফেলুন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন:105 x 105।
-
একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি i, j, একটি অ্যারে v,
লাগবে -
ret :=inf
-
যদি i> j, তাহলে −
-
রিটার্ন 0
-
-
যদি আমি j এর মত হয়, তাহলে −
-
রিটার্ন 1
-
-
যদি j - i 1 এর মত হয়, তাহলে −
-
প্রত্যাবর্তন (যদি v[i] v[j] এর মত হয়, তাহলে 1, অন্যথায় 2)
-
-
যদি i + 1 <=j এবং v[i] একই হয় v[i + 1], তাহলে −
-
ret :=1 + dfs(i + 2, j, v)
-
-
যদি dp[i, j] -1 এর সমান না হয়, তাহলে −
-
dp[i, j]
ফেরত দিন
-
-
ret :=সর্বনিম্ন (ret, 1 + (সর্বনিম্ন (dfs(i + 1, j, v) এবং dfs(i, j - 1, v)))
-
যদি v[i] v[j] এর মত হয়, তাহলে −
-
ret :=সর্বনিম্ন ret এবং dfs(i + 1, j - 1, v)
-
-
শুরু করার জন্য k :=i + 2, যখন k
-
যদি v[i] হয় v[k] এর মতো, তাহলে &minnus;
-
ret :=সর্বনিম্ন ret এবং dfs((i + 1, k - 1, v) + dfs(k + 1, j, v))
-
-
-
রিটার্ন dp[i, j] =ret
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
-1
দিয়ে dp পূরণ করুন -
n :=সংখ্যার আকার
-
রিটার্ন dfs(0, n - 1, nums)
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
int dp[105][105];
int dfs(int i,int j, vector <int>& v){
int ret= INT_MAX;
if(i > j)
return 0;
if(i == j)
return 1;
if(j - i == 1){
return v[i] == v[j] ? 1 : 2;
}
if(i + 1 <= j && v[i] == v[i + 1]){
ret = 1 + dfs(i + 2, j, v);
}
if(dp[i][j] != -1) return dp[i][j];
ret = min({ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v))});
if(v[i] == v[j]){
ret = min(ret, dfs(i + 1, j - 1, v));
}
for(int k = i + 2; k < j; k++){
if(v[i] == v[k]){
ret = min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v));
}
}
return dp[i][j] = ret;
}
int solve(vector<int>& nums) {
memset(dp , -1, sizeof dp);
int n = nums.size();
return dfs(0, n - 1, nums);
}
int main(){
vector<int> v = {6, 2, 4, 4, 2, 10, 6};
cout << solve(v);
} ইনপুট
{6, 2, 4, 4, 2, 10, 6} আউটপুট
2
