समस्या कथन
केवल पूर्णांक के रूप में वर्णों वाली एक स्ट्रिंग को देखते हुए। हमें इस स्ट्रिंग के सभी वर्णों को कम से कम चरणों में हटाने की आवश्यकता है जहां एक चरण में हम सबस्ट्रिंग को हटा सकते हैं जो एक पैलिंड्रोम है। एक सबस्ट्रिंग को हटाने के बाद शेष भागों को जोड़ दिया जाता है।
उदाहरण
यदि इनपुट स्ट्रिंग 3441213 है तो न्यूनतम 2 चरणों की आवश्यकता है
- सबसे पहले स्ट्रिंग से 121 को हटा दें। अब शेष स्ट्रिंग 3443 है
- शेष स्ट्रिंग को पैलिंड्रोम के रूप में निकालें
एल्गोरिदम
हम इस समस्या को हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग कर सकते हैं
1. Let dp[i][j] denotes the number of steps it takes to delete the substring s[i, j] 2. Each character will be deleted alone or as part of some substring so in the first case we will delete the character itself and call subproblem (i+1, j) 3. In the second case we will iterate over all occurrence of the current character in right side, if K is the index of one such occurrence then the problem will reduce to two subproblems (i+1, K – 1) and (K+1, j) 4. We can reach to this subproblem (i+1, K-1) because we can just delete the same character and call for mid substring 5. We need to take care of a case when first two characters are same in that case we can directly reduce to the subproblem (i+2, j)
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(string str) {
int n = str.length();
int dp[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 0;
}
}
for (int len = 1; len <= n; len++) {
for (int i = 0, j = len - 1; j < n; i++, j++) {
if (len == 1)
dp[i][j] = 1;
else {
dp[i][j] = 1 + dp[i + 1][j];
if (str[i] == str[i + 1]) {
dp[i][j] = min(1 + dp[i+ 2][j], dp[i][j]);
}
for (int K = i + 2; K <= j; K++){
if (str[i] == str[K]) {
dp[i][j] =
min(dp[i+1][K-1] + dp[K+1][j], dp[i][j]);
}
}
}
}
}
return dp[0][n - 1];
}
int main() {
string str = "3441213";
cout << "Minimum required steps: " <<
getMinRequiredSteps(str) << endl;
return 0;
} जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है
आउटपुट
Minimum required steps: 2