अस्वीकरण: नीचे वर्णित विधि सार्वभौमिक नहीं है, लेकिन यह अक्सर समस्या का समाधान कर सकती है या आपको सही समाधान तक पहुंचने में मदद कर सकती है।
यदि समस्या इस तथ्य पर उबलती है कि सरणी को गैर-अंतर्विभाजक उपखंडों (लगातार तत्वों का एक क्रम) में एक इष्टतम तरीके से विभाजित करना आवश्यक है (या उपयुक्त विभाजन की संख्या की गणना करें), तो इसे हल करने की कोशिश करने लायक है गतिशील प्रोग्रामिंग का उपयोग करना।
एक उदाहरण समाधान योजना इस प्रकार है:
dp[i] - पहले i तत्वों के लिए प्रतिक्रिया
गिनती dp[i]: चूँकि हम केवल पहले i तत्वों पर विचार कर रहे हैं, i-th तत्व अंतिम होगा, जिसका अर्थ है कि यह तत्व अंतिम उपखंड में होगा और साथ ही, वहाँ सबसे दाहिनी ओर होगा। इसलिए, हम अंतिम उपखंड j की बाईं सीमा पर पुनरावृति कर सकते हैं। गणना की प्रक्रिया में, हम इस उपखंड के मूल्य की गणना करेंगे, और यदि यह सही है, तो हम dp[i] के माध्यम से dp[j - 1] और उपखंड [j;i] के मूल्य की पुनर्गणना करेंगे।
निम्नलिखित सरल समस्या पर विचार करें: पूर्णांकों की एक सरणी दी गई है, आपको इसे गैर-प्रतिच्छेदी उपखंडों की न्यूनतम संख्या में विभाजित करने की आवश्यकता है ताकि प्रत्येक संख्या किसी उपखंड में शामिल हो और प्रत्येक उपखंड में समान संख्याएं हों। उदाहरण के लिए, एक सरणी 1 2 2 3 3 3 2 1 1 के लिए, इष्टतम विभाजन इस तरह दिखता है: [1] [2 2] [3 3 3] [2] [1 1]। यह कार्य केवल सरणी से गुजरकर आसानी से हल हो जाता है (हम सभी समान तत्वों को एक उपखंड में रखते हैं), लेकिन हम इसे एक उदाहरण के लिए गतिशील प्रोग्रामिंग का उपयोग करके हल करेंगे।
इंटन;
सिने>> एन;
// 1-इंडेक्स के साथ सरणी भरें
वेक्टर आगमन (एन + 1);
के लिए (int i = 1; i <= n; i++)
सिने>> आगमन [मैं];
// शुरू में + oo को dp मान पर सेट करें
वेक्टर <इंट> डीपी (एन + 1, 1000000000);
// लंबाई शून्य की एक सरणी को विभाजित करने की आवश्यकता नहीं है, इसलिए इसका उत्तर 0 है
डीपी [0] = 0;
// डीपी [i] के लिए आरोही i में उत्तर की गणना करें
for (int i = 1; i <= n; i++) {
// वर्तमान में गिरफ्तार [i] अंतिम तत्व है, इसलिए यह अंतिम उपखंड में सबसे सही संख्या होगी
// उन सभी विकल्पों के माध्यम से लूप करें जहां यह अंतिम उपखंड शुरू हुआ था
के लिए (int j = i; j > 0; j--) {
अगर (आगमन [जे]! = आगमन [मैं]) {
// यदि आप किसी ऐसे तत्व से मिलते हैं जो पिछले एक के बराबर नहीं है, तो उपखंड में अलग-अलग संख्याएँ होंगी, और यह स्थिति के अनुकूल नहीं है
// जारी रखने का कोई मतलब नहीं है, क्योंकि बाएं बॉर्डर को बाईं ओर ले जाने पर, यह तत्व गायब नहीं होगा, इसलिए हम टूट जाते हैं
तोड़ना;
}
// कल्पना कीजिए कि अंतिम उपखंड था [जे; मैं]
// इसलिए आपको पहले j-1 तत्वों का इष्टतम विभाजन लेने और 1 जोड़ने की आवश्यकता है (उपखंड [j; i] स्वयं)
डीपी [i] = मिन (डीपी [i], डीपी [जे - 1] + 1);
}
}
cout << डीपी [एन];
यदि तत्व किसी भी उपखंड से संबंधित नहीं हो सकते हैं, तो आपको उचित विकल्प पर विचार करने की आवश्यकता है, जैसे dp[i] = dp[i - 1]