मान लीजिए हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है। अब आइए एक ऑपरेशन पर विचार करें जहां हम कुछ सबलिस्ट को हटाते हैं जो एक पैलिंड्रोम है। हमें आवश्यक न्यूनतम संख्या में संचालन की आवश्यकता है ताकि सूची खाली हो।
इसलिए, यदि इनपुट अंकों की तरह है =[6, 2, 4, 4, 2, 10, 6], तो आउटपुट 2 होगा, क्योंकि हम सबलिस्ट [2, 4, 4, 2] को पहले हटा सकते हैं। सूची इस तरह है [6, 10, 6] यह भी एक पैलिंड्रोम है, इसलिए सूची को खाली करने के लिए इसे हटा दें।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
आकार की एक सरणी dp परिभाषित करें:105 x 105।
-
फ़ंक्शन dfs() को परिभाषित करें, इसमें i, j, एक सरणी v,
. लगेगा -
रिट :=inf
-
अगर मैं> जे, तो -
-
वापसी 0
-
-
यदि i, j के समान है, तो -
-
वापसी 1
-
-
अगर j - i 1 के समान है, तो -
-
वापसी (यदि v[i] v[j] के समान है, तो 1, अन्यथा 2)
-
-
यदि i + 1 <=j और v[i], v[i + 1] के समान है, तो -
-
रिट :=1 + dfs(i + 2, j, v)
-
-
अगर dp[i, j] -1 के बराबर नहीं है, तो -
-
वापसी डीपी [i, जे]
-
-
ret :=न्यूनतम (ret, 1 + (न्यूनतम (dfs(i + 1, j, v) और dfs(i, j-1, v)))
-
यदि v[i], v[j] के समान है, तो -
-
ret :=न्यूनतम रिट और dfs(i + 1, j-1, v)
-
-
k :=i + 2 को इनिशियलाइज़ करने के लिए, जब k
-
अगर v[i], v[k] के समान है, तो &minnus;
-
ret :=न्यूनतम रिट और dfs((i + 1, k-1, v) + dfs(k + 1, j, v))
-
-
-
वापसी डीपी [i, जे] =सेवानिवृत्त
-
मुख्य विधि से निम्न कार्य करें -
-
dp को -1 से भरें
-
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
