गतिशील प्रोग्रामिंग में पैटर्न

अस्वीकरण: नीचे वर्णित विधि सार्वभौमिक नहीं है, लेकिन यह अक्सर समस्या का समाधान कर सकती है या आपको सही समाधान तक पहुंचने में मदद कर सकती है।

यदि समस्या इस तथ्य पर उबलती है कि सरणी को गैर-अंतर्विभाजक उपखंडों (लगातार तत्वों का एक क्रम) में एक इष्टतम तरीके से विभाजित करना आवश्यक है (या उपयुक्त विभाजन की संख्या की गणना करें), तो इसे हल करने की कोशिश करने लायक है गतिशील प्रोग्रामिंग का उपयोग करना।

एक उदाहरण समाधान योजना इस प्रकार है:
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]

यदि सरणी को ठीक k उपखंडों में विभाजित करना आवश्यक है, तो दूसरा पैरामीटर केवल गतिशील प्रोग्रामिंग में जोड़ा जाता है - कितने खंडों को विभाजित करना है।
यानी अब हम निम्नलिखित डीपी पर विचार करेंगे:
dp[i][j] पहले i तत्वों का उत्तर है, अगर हम उन्हें बिल्कुल j खंडों में विभाजित करें।
अमान्य स्थितियों से सावधान रहें।

गतिकी की पुनर्गणना समान है, लेकिन दूसरे पैरामीटर को ध्यान में रखते हुए। यही है, डीपी [i] [के] की गिनती और अंतिम उपखंड जे की बाईं सीमा के माध्यम से छंटनी, हम डीपी [i] [के] के माध्यम से डीपी [जे - 1] [के - 1] और खंड के मूल्य की पुनर्गणना करते हैं [जे; मैं]।

अस्वीकरण: नीचे वर्णित विधि सार्वभौमिक नहीं है, लेकिन यह अक्सर समस्या का समाधान कर सकती है या आपको सही समाधान तक पहुंचने में मदद कर सकती है।

यदि कुछ अक्ष (आमतौर पर समय अक्ष या किसी सरणी के सूचकांक) पर स्थित अंतराल का एक सेट है और आपको उनमें से कुछ को इष्टतम तरीके से चुनने की आवश्यकता है ताकि चयनित अंतराल प्रतिच्छेद न करें, तो आपको गतिशील प्रोग्रामिंग का उपयोग करने का प्रयास करना चाहिए

अनुमानित समाधान योजना:

प्रारंभ में, हम उपलब्ध अंतराल को सही सीमा के अनुसार क्रमबद्ध करते हैं। आइए निम्नलिखित गतिशीलता शुरू करें: dp[i] - पहले i अंतराल के लिए उत्तर। 
हम निम्नानुसार पुनर्गणना करेंगे: पहले, इस स्थिति पर विचार करें कि इस अंतराल का उपयोग नहीं किया जाएगा, फिर बस dp[i] = dp[i-1]। ध्यान दें कि यह सुनिश्चित करता है कि जैसे-जैसे i बढ़ता है dp[i] का मान घटता नहीं है। और यह तार्किक है, क्योंकि। एक नया अंतर जोड़कर, हम वैश्विक उत्तर को खराब नहीं कर सकते: या तो हम नए अंतर को अनदेखा कर देते हैं, या हम इसका उपयोग करके एक अधिक लाभदायक संस्करण का निर्माण करते हैं। अब, यदि हम i-th गैप का उपयोग करना चाहते हैं, तो हम उन गैप्स का उपयोग कर सकते हैं, जिनकी दाहिनी सीमाएँ वर्तमान गैप की बाईं सीमा से कम हैं, क्योंकि हमें नॉन-ओवरलैपिंग गैप का एक सेट चुनना होगा। ऐसा करने के लिए, हमने शुरू में अंतराल को सही सीमा से क्रमबद्ध किया, ताकि अब हम आवश्यक स्थिति को कुशलतापूर्वक ढूंढ सकें। यदि संभव हो तो यह विश्लेषणात्मक रूप से किया जा सकता है, लेकिन सामान्य मामले में एक बिनसर्च के साथ एक अंतर खोजना संभव है, जिसकी दाहिनी सीमा वर्तमान की बाईं सीमा से कम है और साथ ही, अधिकतम संभव एक। हम लालची कारणों से सही सीमा को अधिकतम करना चाहते हैं, क्योंकि जैसे-जैसे मैं बढ़ता हूं, उत्तर केवल बढ़ सकता है। तदनुसार, हम आवश्यक स्थिति p पाते हैं और dp[i] को dp[p] और i-th अंतराल के माध्यम से पुनर्गणना करते हैं।