समस्या कथन
एक स्ट्रिंग दी गई है जिसमें केवल पूर्णांक के रूप में वर्ण हैं। हमें इस स्ट्रिंग के सभी वर्णों को न्यूनतम चरणों में हटाना है जहां एक चरण में हम वह सबस्ट्रिंग हटा सकते हैं जो पेलिंड्रोम है। सबस्ट्रिंग हटाने के बाद शेष भाग संयोजित हो जाते हैं।
उदाहरण
यदि इनपुट स्ट्रिंग 3441213 है तो न्यूनतम 2 चरण आवश्यक हैं
- पहले स्ट्रिंग से 121 हटाएं। अब शेष स्ट्रिंग 3443 है
- शेष स्ट्रिंग को हटाएं क्योंकि यह पेलिंड्रोम है
एल्गोरिदम
हम इस समस्या को हल करने के लिए डायनामिक प्रोग्रामिंग का उपयोग कर सकते हैं
1. मान लें dp[i][j] सबस्ट्रिंग s[i, j] को हटाने में लगने वाले चरणों की संख्या को दर्शाता है 2. प्रत्येक वर्ण को अकेले या किसी सबस्ट्रिंग के भाग के रूप में हटाया जाएगा इसलिए पहले मामले में हम वर्ण को स्वयं हटाएंगे और सबप्रॉब्लम (i+1, j) को कॉल करेंगे 3. दूसरे मामले में हम वर्तमान वर्ण की दाईं ओर सभी घटनाओं पर पुनरावृति करेंगे, यदि K ऐसी किसी घटना का इंडेक्स है तो समस्या दो सबप्रॉब्लम (i+1, K - 1) और (K+1, j) तक कम हो जाएगी 4. हम इस सबप्रॉब्लम (i+1, K-1) तक पहुंच सकते हैं क्योंकि हम समान वर्ण को हटा सकते हैं और मध्य सबस्ट्रिंग के लिए कॉल कर सकते हैं 5. हमें उस मामले का ध्यान रखने की आवश्यकता है जब पहले दो वर्ण समान हों उस स्थिति में हम सीधे सबप्रॉब्लम (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 << "न्यूनतम आवश्यक चरण: " << getMinRequiredSteps(str) << endl; return 0; }जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है
आउटपुट
न्यूनतम आवश्यक चरण: 2