👳🏿 🔏 🧕🏾 सब कुछ आप गतिशील प्रोग्रामिंग के बारे में जानना चाहते थे, लेकिन पूछने से डरते थे 😈 🧗🏽 🥡

मैं गतिशील प्रोग्रामिंग (बाद में बस डायनामिक्स के रूप में संदर्भित) के बारे में कुछ लेख पाकर बेहद हैरान था यह हमेशा मुझे प्रतीत हुआ कि यह प्रतिमान काफी व्यापक है, जिसमें प्रोग्रामिंग ओलिंपियाड्स की सीमाओं से परे भी शामिल है। इसलिए, मैं अपने लेख के साथ इस अंतर को बंद करने की कोशिश करूंगा।

#        Python

मूल बातें

शायद एक वाक्य में मैंने डायनामिक्स का सबसे अच्छा वर्णन सुना है:

डायनेमिक प्रोग्रामिंग तब होती है जब हमारे पास एक कार्य होता है जो स्पष्ट नहीं है कि कैसे हल किया जाए, और हम इसे छोटे कार्यों में तोड़ देते हैं, जो यह भी स्पष्ट नहीं है कि कैसे हल किया जाए। (c) ए। कुमोक

आप की जरूरत है गतिशीलता द्वारा समस्या को सफलतापूर्वक हल करने के लिए:
1) डायनेमिक्स स्थिति: पैरामीटर (एस) जो विशिष्ट रूप से एक उपमा निर्दिष्ट करता है।
2) प्रारंभिक अवस्थाओं के मूल्य।
3) राज्यों के बीच संक्रमण: पुनर्गणना सूत्र।
4) भर्ती के लिए प्रक्रिया।
5) समस्या के उत्तर की स्थिति: कभी-कभी यह योग होता है या, उदाहरण के लिए, कई राज्यों के मूल्यों का अधिकतम।

पुनर्गणना प्रक्रिया

तीन रूपांतरण आदेश हैं:
1) प्रत्यक्ष आदेश:
राज्य क्रमिक रूप से पहले से गणना किए गए लोगों के आधार पर पुनर्गणना किए जाते हैं।

2) रिवर्स ऑर्डर:
सभी स्थिति वर्तमान स्थिति के आधार पर अपडेट की जाती हैं।

3) आलसी गतिकी:
पुनरावर्ती ने डायनामिक्स के पुनरावृत्ति समारोह को याद किया। यह एक चक्रीय राज्य ग्राफ पर एक गहरी खोज की तरह कुछ है, जहां किनारों उनके बीच निर्भरताएं हैं।

प्राथमिक उदाहरण: फाइबोनैचि संख्या । स्थिति - संख्या संख्या।

प्रत्यक्ष आदेश:

 fib[1] = 1 #   fib[2] = 1 #   for i in range(3, n + 1): fib[i] = fib[i - 1] + fib[i - 2] #   i

रिवर्स ऑर्डर:

 fib[1] = 1 #   for i in range(1, n): fib[i + 1] += fib[i] #   i + 1 fib[i + 2] += fib[i] #   i + 2

आलसी गतिशीलता:

 def get_fib(i): if (i <= 2): #   return 1 if (fib[i] != -1): #  return fib[i] fib[i] = get_fib(i - 1) + get_fib(i - 2) #  return fib[i]

तीनों विकल्पों में जीवन का अधिकार है। उनमें से प्रत्येक का अपना दायरा है, हालांकि अक्सर दूसरों के साथ अतिव्यापी।

बहुआयामी गतिशीलता

"रूपांतरण के क्रम" में, एक आयामी गतिशीलता का एक उदाहरण ऊपर दिया गया है, इसलिए मैं तुरंत बहुआयामी के साथ शुरू करूँगा। यह एक आयामी से भिन्न होता है, जैसा कि आप शायद अनुमान लगाते हैं, माप की संख्या, अर्थात्, राज्य में मापदंडों की संख्या। इस आधार पर वर्गीकरण आमतौर पर "एक-दो-कई" योजना पर आधारित होता है और वास्तव में मौलिक नहीं होता है।

बहुआयामी गतिकी एक-आयामी से बहुत भिन्न नहीं होती है, जिसे आप कुछ उदाहरणों को देखकर देख सकते हैं:

उदाहरण नंबर 1: एसएमएस की संख्या

पहले, जब फोन में बटन होते थे, उनके कीबोर्ड कुछ इस तरह दिखते थे:

यह गणना करना आवश्यक है कि इस तरह के कीबोर्ड पर k नल से अधिक का उपयोग करके कई अलग-अलग पाठ संदेश कितने लिखने हैं।

निर्णय

1) डायनेमिक्स स्थिति: dp[n][m] - m नल के उपयोग से लंबाई n के विभिन्न संदेशों की संख्या।
2) प्रारंभिक स्थिति: शून्य क्लिक का उपयोग करते हुए लंबाई शून्य का एक संदेश है - खाली।
3) पुनर्गणना सूत्र: प्रत्येक के लिए आठ अक्षर होते हैं, जिन्हें लिखने के लिए आपको एक, दो और तीन क्लिक की आवश्यकता होती है, साथ ही दो अक्षरों की आवश्यकता होती है।

प्रत्यक्ष भर्ती:

 dp[n][m] = (dp[n - 1][m - 1] + dp[n - 1][m - 2] + dp[n - 1][m - 3]) * 8 + dp[n - 1][m - 4] * 2

रिवर्स एक्सचेंज:

 dp[n + 1][m + 1] += dp[n][m] * 8 dp[n + 1][m + 2] += dp[n][m] * 8 dp[n + 1][m + 3] += dp[n][m] * 8 dp[n + 1][m + 4] += dp[n][m] * 2

4) रूपांतरण प्रक्रिया:
यदि आप सीधे लिखते हैं, तो आपको गतिशीलता सीमा से परे जाने के बारे में अलग से सोचने की जरूरत है, उदाहरण के लिए, जब हम dp[n - 1][m - 4] ओर मुड़ते हैं, जो कि छोटे m लिए मौजूद नहीं हो सकता है। इसे दरकिनार करने के लिए, आप या तो चेक सेट कर सकते हैं या तटस्थ तत्वों को लिख सकते हैं (जो उत्तर नहीं बदलते हैं)।

रीकाउंट का उपयोग करते समय, सब कुछ सरल है: हम हमेशा आगे बढ़ते हैं, ताकि हम नकारात्मक तत्वों में न जाएं।

5) उत्तर सभी राज्यों का योग है।

युपीडी:
दुर्भाग्य से, मैंने एक गलती की - राज्य से संदेश n की लंबाई को हटाकर समस्या को एक-मंद रूप से हल किया जा सकता है।
1) स्थिति: dp[m] - विभिन्न संदेशों की संख्या जो m क्लिक में टाइप की जा सकती हैं।
2) प्रारंभिक अवस्था: dp[0] = 1 ।
3) पुनर्गणना सूत्र:

 dp[m] = (dp[m - 1] + dp[m - 2] + dp[m - 3]) * 8 + dp[m - 4] * 2

4) आदेश: सभी तीन विकल्पों का उपयोग किया जा सकता है।
5) उत्तर सभी राज्यों का योग है।

उदाहरण 2: घोड़ा

एक शतरंज का घोड़ा आकार के बोर्ड पर पिंजरे (1, 1) में खड़ा होता है M सेल (N, M) को चार प्रकार के चरणों में ले जाने के तरीकों की संख्या की गणना करना आवश्यक है:

निर्णय

1) गतिशीलता राज्य: dp[i][j] - (i, j) को प्राप्त करने के तरीकों की संख्या।
2) प्रारंभिक मूल्य: आप सेल (1, 1) एक तरह से प्राप्त कर सकते हैं - कुछ भी नहीं करें।
3) पुनर्गणना सूत्र:
सीधे आदेश के लिए:

 dp[i][j] = dp[i - 2][j - 1] + dp[i - 2][j + 1] + dp[i - 1][j - 2] + dp[i + 1][j - 2]

रिवर्स ऑर्डर के लिए:

 dp[i + 1][j + 2] += dp[i][j] dp[i + 2][j + 1] += dp[i][j] dp[i - 1][j + 2] += dp[i][j] dp[i + 2][j - 1] += dp[i][j]

4) और अब इस कार्य में सबसे दिलचस्प हिस्सा: आदेश। यहां आप केवल पंक्तियों या स्तंभों के माध्यम से नहीं ले जा सकते हैं। क्योंकि अन्यथा हम उन राज्यों का उल्लेख करेंगे जिन्हें अभी तक एक प्रत्यक्ष क्रम में पुनर्गणना नहीं हुई है, और हम अभी भी अधूरे राज्यों को रिवर्स दृष्टिकोण के साथ ले जाएंगे।

इसके दो तरीके हैं:
1) एक अच्छा समाधान के साथ आओ।
2) आलसी गत्यात्मकता को चलाएं, उसे यह पता लगाने दें।

यदि आप सोचने के लिए बहुत आलसी हैं - हम आलसी गतिशीलता शुरू करते हैं, तो यह पूरी तरह से कार्य के साथ सामना करेगा।
यदि आलस्य नहीं है, तो आप इस तरह से वर्कअराउंड के बारे में सोच सकते हैं:

यह आदेश प्रत्यक्ष चरण में प्रत्येक चरण में आवश्यक सभी कोशिकाओं के प्रसंस्करण, और इसके विपरीत में वर्तमान स्थिति के प्रसंस्करण की गारंटी देता है।

5) उत्तर केवल dp[n][m] में निहित है।

गतिशीलता और संक्रमण मैट्रिक्स

यदि आपने कभी भी मैट्रिसेस को गुणा नहीं किया है, लेकिन इस शीर्षक को समझना चाहते हैं, तो आपको कम से कम विकि पढ़ना चाहिए।

मान लीजिए कि एक समस्या है जिसे हमने पहले से ही गतिशील प्रोग्रामिंग द्वारा हल किया है, उदाहरण के लिए, अनन्त फाइबोनैचि संख्या।
इसे थोड़ा सुधारते हैं। हमारे पास एक वेक्टर है

जिससे हम वेक्टर प्राप्त करना चाहते हैं

। आइए सूत्रों को थोड़ा खोलें:

। आप इसे वेक्टर से देख सकते हैं

वेक्टर प्राप्त कर सकते हैं

किसी प्रकार के मैट्रिक्स से गुणा करके, क्योंकि पहले वेक्टर से केवल मुड़ा हुआ चर अंतिम वेक्टर में दिखाई देता है। इस मैट्रिक्स को प्राप्त करना आसान है, यहाँ यह है:

। हम इसे संक्रमण मैट्रिक्स कहते हैं।

इसका मतलब है कि यदि आप वेक्टर लेते हैं

और इसे संक्रमण मैट्रिक्स n - 1 गुणा करें n - 1 बार, हम वेक्टर प्राप्त करते हैं

, जिसमें fib[n] निहित है - समस्या का उत्तर।

और अब, यह सब क्यों आवश्यक है। मैट्रिक्स गुणन में संबद्धता की संपत्ति है, अर्थात।

(लेकिन इसमें कम्यूटिटी नहीं है, जो मेरी राय में आश्चर्यजनक है)। यह संपत्ति हमें ऐसा करने का अधिकार देती है:

।

यह अच्छा है क्योंकि अब आप तीव्र घातांक विधि लागू कर सकते हैं, जो इसके लिए काम करता है

। कुल मिलाकर, हम अंकगणितीय परिचालनों के लघुगणक के लिए N फाइबोनैचि संख्या की गणना करने में सक्षम थे।

और अब उदाहरण अधिक गंभीर है:

उदाहरण संख्या 3: सवथोथ अनुक्रम

हम लंबाई N के sawtooth अनुक्रम को उस अनुक्रम के रूप में निरूपित करते हैं जिसके लिए प्रत्येक चरम तत्व की स्थिति पूरी नहीं होती है: यह या तो उसके दो पड़ोसियों से कम है या अधिक है। यह लंबाई N के अंकों के sawtooth दृश्यों की संख्या की गणना करने के लिए आवश्यक है N यह कुछ इस तरह दिखता है:

निर्णय

संक्रमण मैट्रिक्स के बिना एक समाधान के साथ शुरू करने के लिए:

1) डायनामिक्स स्थिति: dp[n][last][less] - last अंक के साथ लंबाई n के आरी अनुक्रमों की संख्या। और यदि less == 0 , तो अंतिम अंक एक से कम है, और यदि less == 1 , तो अधिक है।
2) प्रारंभिक मूल्य:

 for last in range(10): dp[2][last][0] = 9 - last dp[2][last][1] = last

3) गतिशीलता की पुनर्गणना:

 for prev in range(10): if prev > last: dp[n][last][0] += dp[n - 1][prev][1] if prev < last: dp[n][last][1] += dp[n - 1][pref][0]

4) पुनर्गणना आदेश: हम हमेशा पिछली लंबाई का उल्लेख करते हैं, इसलिए सिर्फ कुछ के लिए नेस्टेड है।
5) उत्तर योग dp[N][0..9][0..1] ।

अब हमें एक प्रारंभिक वेक्टर और एक संक्रमण मैट्रिक्स के साथ आने की जरूरत है। वेक्टर को जल्दी से आविष्कार किया गया लगता है: सभी राज्य अनुक्रम N की लंबाई को दर्शाते हैं N खैर, रूपांतरण मैट्रिक्स व्युत्पन्न है, रूपांतरण सूत्रों को देखते हुए।

वेक्टर और संक्रमण मैट्रिक्स

सबसिडी डायनेमिक्स

यह एक डायनामिक्स क्लास है, जिसमें राज्य किसी ऐरे की अधीनता की सीमा है। लब्बोलुआब यह है कि हमारे सरणी के सभी संभव उप-खंडों के आधार पर उप-मुखौटे के उत्तरों की गणना करना है। आमतौर पर उन्हें बढ़ती लंबाई के क्रम में क्रमबद्ध किया जाता है, और गणना छोटे खंडों पर क्रमशः आधारित होती है।

उदाहरण 4: एक स्ट्रिंग पैकिंग

यहाँ विस्तारित स्थिति है । मैं संक्षेप में इसे फिर से बताऊंगा:

एक संकुचित रेखा को परिभाषित करें:
1) केवल अक्षरों से युक्त एक स्ट्रिंग एक संकुचित स्ट्रिंग है। वह खुद को अशुद्ध करती है।
2) एक स्ट्रिंग जो दो संकुचित तारों A और B का एक संयोजन है B इसका विस्तार विस्तारित पंक्तियों A और B को जोड़ने के लिए किया जाता है B
3) स्ट्रिंग D(X) , जहां D 1 से अधिक पूर्णांक है, और X एक संकुचित स्ट्रिंग है। यह X से विघटित D स्ट्रिंग्स के संघटन में विघटित होता है।
उदाहरण: “3(2(A)2(B))C” “AABBAABBAABBC” में विस्तारित है।

यह लाइन s द्वारा आवश्यक है कि इसमें सबसे छोटी संकुचित लाइन की लंबाई का पता लगाया जाए।

निर्णय

यह समस्या हल हो रही है, जैसा कि आप शायद पहले से ही अनुमान लगा चुके हैं, उप-खंडों की गतिशीलता से।

1) डायनेमिक्स स्थिति: d[l][r] - न्यूनतम लंबाई की एक संकुचित स्ट्रिंग एक स्ट्रिंग s[l:r] में विस्तारित होती है
2) प्रारंभिक अवस्था: लंबाई के सभी सब्सट्रेट केवल उनमें संपीड़ित हो सकते हैं।
3) गतिशीलता की पुनर्गणना:
सबसे अच्छे उत्तर में किसी प्रकार का अंतिम संपीड़न ऑपरेशन होता है: या तो यह केवल बड़े अक्षरों का एक स्ट्रिंग है, या यह दो लाइनों का एक संयोजन है, या स्वयं संपीड़न है। तो चलो सभी विकल्पों के माध्यम से जाते हैं और सबसे अच्छा एक का चयन करते हैं।

 dp_len = r - l dp[l][r] = dp_len #    -  . for i in range(l + 1, r): dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) #       for cnt in range(2, dp_len): if (dp_len % cnt == 0): #   ,      good = True for j in range(1, (dp_len / cnt) + 1): #   ,   cnt   good &= s[l:l + dp_len / cnt] == s[l + (dp_len / cnt) * j:l + (dp_len / cnt) * (j + 1)] if good: #    cnt     dp[l][r] = min(dp[l][r], len(str(cnt)) + 1 + dp[l][l + dp_len / cnt] + 1)

4) पुनरावर्ती के लिए प्रक्रिया: घटिया या आलसी गतिशीलता की सीधी आरोही लंबाई।
5) उत्तर d[0][len(s)] में निहित है।

उदाहरण नंबर 5: ओक्स

सबट्री डायनामिक्स

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

उदाहरण 6: तार्किक पेड़

एक निलंबित पेड़ को देखते हुए, पत्तियों में एकल-बिट संख्या होती है - 0 या 1 । संख्याएँ सभी आंतरिक शीर्षकों में भी लिखी जाती हैं, लेकिन निम्नलिखित नियम के अनुसार: प्रत्येक शीर्ष के लिए तार्किक परिचालनों में से एक का चयन किया जाता है: "AND" या "OR"। यदि यह "और" है, तो चोटी का मूल्य उसके सभी बच्चों के मूल्यों का तार्किक "और" है। यदि "ओआर" है, तो वर्टेक्स का मूल्य उसके सभी बच्चों के मूल्यों का एक तार्किक "ओआर" है।

आंतरिक कार्यक्षेत्रों में तार्किक परिचालनों में न्यूनतम संख्या में परिवर्तन की आवश्यकता होती है, जैसे कि जड़ में मूल्य परिवर्तन या सूचित करना कि यह असंभव है।

निर्णय

1) डायनामिक्स स्थिति: d[v][x] - शीर्ष पर x का मान प्राप्त करने के लिए आवश्यक संचालन की संख्या। यदि यह संभव नहीं है, तो राज्य मूल्य +inf ।
2) प्रारंभिक मूल्य: पत्तियों के लिए, यह स्पष्ट है कि व्यक्ति शून्य परिवर्तन के लिए किसी का मान प्राप्त कर सकता है, लेकिन मूल्य को बदलना असंभव है, अर्थात यह संभव है, लेकिन केवल +inf संचालन के लिए।
3) पुनर्गणना सूत्र:
यदि शीर्ष पर पहले से ही मान x , तो शून्य है। यदि नहीं, तो दो विकल्प हैं: वर्तमान शीर्ष पर ऑपरेशन को बदलें या नहीं। दोनों के लिए, आपको सबसे अच्छा विकल्प खोजने और सर्वश्रेष्ठ चुनने की आवश्यकता है।

यदि ऑपरेशन "और" और आपको "0" प्राप्त करने की आवश्यकता है, तो इसका उत्तर न्यूनतम मान d[i][0] , जहां i v का बेटा i ।
यदि ऑपरेशन "और" और आपको "1" प्राप्त करने की आवश्यकता है, तो उत्तर सभी मूल्यों का योग है d[i][1] , जहां i v का बेटा i ।
यदि ऑपरेशन "ओआर" और आपको "0" प्राप्त करने की आवश्यकता है, तो उत्तर सभी मूल्यों का योग है d[i][0] , जहां i v का बेटा i ।
यदि ऑपरेशन "ओआर" और आपको "1" प्राप्त करने की आवश्यकता है, तो इसका उत्तर न्यूनतम मान d[i][1] , जहां i v का बेटा i ।

4) पुनर्गणना क्रम: यह सबसे आसानी से आलसी रूप से लागू किया जाता है - जड़ से गहराई में खोज के रूप में।
5) उत्तर d[root][value[root] xor 1] ।

सबसेट डायनामिक्स

सबसेट पर डायनामिक्स में, दिए गए सेट का एक मुखौटा आमतौर पर एक राज्य में प्रवेश करता है। वे इस मुखौटा में इकाइयों की संख्या बढ़ाने के क्रम में सबसे अधिक बार चुने जाते हैं और शामिल किए गए राज्यों से क्रमश: छोटे होते हैं। आमतौर पर आलसी गतिशीलता का उपयोग किया जाता है, इसलिए विशेष रूप से वर्कअराउंड के बारे में नहीं सोचना चाहिए, जो कभी-कभी पूरी तरह से तुच्छ नहीं होता है।

उदाहरण नंबर 7: न्यूनतम वजन का हैमिल्टन चक्र, या यात्रा विक्रेता समस्या

एक भारित (बढ़त भार गैर-ऋणात्मक) ग्राफ G आकार N को देखते हुए N न्यूनतम वजन के एक हैमिल्टनियन चक्र (आत्म-चौराहों के बिना सभी कोने से गुजरने वाला चक्र) का पता लगाएं।

निर्णय

चूंकि हम सभी चक्करों से गुजरने वाले चक्र की तलाश कर रहे हैं, इसलिए हम "प्रारंभिक" शीर्ष के लिए कोई भी चुन सकते हैं। इसे शीर्ष संख्या 0 ।

1) डायनेमिक्स स्थिति: dp[mask][v] - वर्टेक्स 0 से वर्टेक्स v तक के न्यूनतम वजन का मार्ग, सभी लंबों से गुजरते हुए जो mask और केवल उनके साथ होते हैं।
2) प्रारंभिक मूल्य: dp[1][0] = 0 , अन्य सभी राज्य शुरू में - +inf ।
3) पुनर्गणना सूत्र: यदि mask में ith बिट 1 और i से v तक एक धार है, तो:

 dp[mask][v] = min(dp[mask][v], dp[mask - (1 << i)][i] + w[i][v])

जहां w[i][v] i से v तक किनारे का वजन है।
4) रूपांतरण प्रक्रिया: सबसे आसान और सबसे सुविधाजनक तरीका आलसी गतिकी लिखना है, लेकिन आप इसमें एकल बिट्स की संख्या बढ़ाने के लिए मुखौटे की गणना को विकृत और लिख सकते हैं।
5) उत्तर d[(1 << N) - 1][0] में निहित है।

प्रोफ़ाइल गतिशीलता

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

इन कार्यों को संपूर्ण खोज द्वारा हल किया जा सकता है

जहां a सेल के टाइलिंग के कई प्रकार हैं। प्रोफ़ाइल के साथ डायनेमिक्स रैखिक के आयामों में से एक में समय का अनुकूलन करता है, केवल गुणांक को अपने आप में तेजी से छोड़ देता है। आपको ऐसा कुछ मिलता है:

।

एक प्रोफ़ाइल k (अक्सर एक) कॉलम है, जो पहले से ही टाइल वाले हिस्से के बीच की सीमा है और अभी तक टाइल नहीं है। यह सीमा केवल आंशिक रूप से भरी हुई है। बहुत बार यह गतिशीलता की स्थिति का हिस्सा होता है।

लगभग हमेशा, एक राज्य एक प्रोफ़ाइल है और यह प्रोफ़ाइल कहाँ है। और संक्रमण एक के बाद एक इस स्थान को बढ़ाता है। आप यह पता कर सकते हैं कि क्या प्रोफ़ाइल के आकार के साथ एक समय में एक प्रोफ़ाइल से दूसरे में स्विच करना संभव है। यह हर बार टोह के दौरान जांचा जा सकता है, लेकिन इसे भी गिना जा सकता है। हम दो आयामी सरणी की गणना can[mask][next_mask] - क्या एक आंकड़े से दूसरे की ओर बढ़ना संभव है, जिससे प्रोफाइल की स्थिति एक से बढ़ जाए। यदि आप गणना करते हैं, तो इसे निष्पादित करने में कम समय लगेगा, और अधिक मेमोरी।

उदाहरण संख्या 8: डोमिनोज़ वर्चस्व

1 x 2 और 2 x 1 आयाम वाले डोमिनोज़ का उपयोग करके तालिका N x M को निकालने के तरीकों की संख्या ज्ञात करें।

निर्णय

यहाँ प्रोफ़ाइल एक एकल स्तंभ है। बाइनरी मास्क के रूप में इसे स्टोर करना सुविधाजनक है: 0 - टाइल वाले कॉलम सेल नहीं, 1 - टाइल वाले। यानी कुल प्रोफाइल

।

0) पूर्व-गणना (वैकल्पिक): प्रोफाइल के सभी जोड़े पर पुनरावृति करें और जांचें कि एक से दूसरे में जा सकते हैं। इस कार्य में, इसे निम्नानुसार सत्यापित किया गया है:

यदि अगले स्थान पर पहली प्रोफ़ाइल 1 , तो दूसरे में यह 0 होना चाहिए, क्योंकि हम किसी भी आकृति के साथ इस सेल को पुल नहीं कर सकते हैं।

यदि अगली जगह पहली प्रोफ़ाइल 0 , तो दो विकल्प हैं - या तो दूसरे 0 या 1 ।
यदि 0 , इसका मतलब है कि हम एक वर्टिकल डोमिनोज़ लगाने के लिए बाध्य हैं, जिसका मतलब है कि अगली सेल को 1 माना जा सकता है। यदि 1 , तो हम एक ऊर्ध्वाधर डोमिनोज़ लगाते हैं और अगले सेल पर जाते हैं।

संक्रमण के उदाहरण (ऊपरी प्रोफ़ाइल से आप निचले लोगों तक जा सकते हैं और केवल उनमें):

उसके बाद, एरे को सब कुछ बचा can[mask][next_mask] - 1 , अगर आप जा सकते हैं, तो 0 - अगर आप नहीं कर सकते हैं।
1) गतिशीलता की अवस्था: dp[pos][mask] - पहले pos - 1 के पूर्ण झुकाव की संख्या pos - 1 प्रोफाइल mask साथ pos - 1 कॉलम।
2) प्रारंभिक अवस्था: dp[0][0] = 1 - क्षेत्र की बाईं सीमा एक सीधी दीवार है।
3) पुनर्गणना सूत्र:

 dp[pos][mask] += dp[pos - 1][next_mask] * can[mask][next_mask]

4) बायपास आदेश - बढ़ती हुई pos क्रम में।
5) उत्तर dp [स्थिति] [0] में है।

परिणामी स्पर्शोन्मुखता है

।

टूटी हुई प्रोफ़ाइल की गतिशीलता

यह प्रोफ़ाइल की गतिशीलता का एक बहुत मजबूत अनुकूलन है। यहां प्रोफ़ाइल न केवल एक मुखौटा है, बल्कि एक फ्रैक्चर साइट भी है। यह इस तरह दिखता है:

अब, प्रोफ़ाइल में एक किंक जोड़ने के बाद, आप अगले राज्य में आगे बढ़ सकते हैं, केवल एक आकृति जोड़कर, किंक के बाएं सेल को कवर कर सकते हैं। यही है, N एक कारक द्वारा राज्यों की संख्या में वृद्धि करके (हमें याद रखना चाहिए कि ब्रेक कहां है), हमने एक राज्य से दूसरे में संक्रमण की संख्या को कम कर दिया

को

। एसिम्पोटिक्स में सुधार हुआ

को

।

डोमिनोज के साथ टाइलिंग की समस्या के उदाहरण द्वारा एक टूटी हुई प्रोफ़ाइल के साथ गतिशीलता में संक्रमण (उदाहरण संख्या 8):

उत्तर वसूली

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

प्रत्येक कार्य का उत्तर बहाल करने का अपना तरीका है, लेकिन सबसे आम:

डायनामिक्स अवस्था के मान के आगे उप-प्रतिक्रिया के लिए पूर्ण प्रतिक्रिया रखें। यदि उत्तर कुछ बड़ा है, तो आपको बहुत अधिक मेमोरी की आवश्यकता हो सकती है, इसलिए यदि आप किसी अन्य विधि का उपयोग कर सकते हैं, तो वे आमतौर पर ऐसा करते हैं।
दी गई स्थिति के पूर्वज (ओं) को जानते हुए, उत्तर को पुनर्स्थापित करें। अक्सर आप उत्तर को पुनर्स्थापित कर सकते हैं, केवल यह जानते हुए कि यह कैसे प्राप्त किया गया था। एक ही "लाइन पैकिंग" में, उत्तर को पुनर्स्थापित करने के लिए, आप केवल अंतिम कार्रवाई और उस स्थिति से स्टोर कर सकते हैं जहां से इसे प्राप्त किया गया था।
एक तरीका है जो अतिरिक्त मेमोरी का उपयोग नहीं करता है - गतिशीलता की पुनर्गणना करने के बाद, अंत से सर्वोत्तम पथ पर जाएं और सड़क के साथ उत्तर लिखें।

मामूली अनुकूलन

स्मृति

अक्सर गतिकी में आप एक ऐसी समस्या को पूरा कर सकते हैं जिसमें एक राज्य को अन्य राज्यों की बहुत बड़ी संख्या की आवश्यकता नहीं होती है। उदाहरण के लिए, फाइबोनैचि संख्याओं की गणना करते समय, हम केवल अंतिम दो का उपयोग करते हैं, और हम पिछले वाले की ओर कभी नहीं मुड़ेंगे। तो, आप उनके बारे में भूल सकते हैं, अर्थात, मेमोरी में स्टोर न करें। कभी-कभी यह स्पर्शोन्मुख स्मृति अनुमान में सुधार करता है। इस तकनीक का उपयोग उदाहरण संख्या 1, नंबर 2, नंबर 3 (संक्रमण मैट्रिक्स के बिना समाधान में), नंबर 7 और नंबर 8 में किया जा सकता है। सच है, यह किसी भी तरह से काम नहीं करेगा यदि बाईपास आदेश आलसी गतिशीलता है।

समय

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

राज्य प्रतिस्थापन

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

उदाहरण संख्या 9: एक संख्या का अपघटन

संख्या के विघटन की संख्या Nको विभिन्न शब्दों में ज्ञात करना आवश्यक है । उदाहरण के लिए, यदि N = 7, तो ऐसे विस्तार 5:

7
3 + 4
२ + ५
1 + 7
1 + 2 + 4

विभिन्न राज्यों के साथ दो समाधान

№1:

1) : dp[n][k] — n , k . k , , .
2) : dp[1][1] = 1 , dp[1][i] = 0 .
3) :

 for last_summand in range(1, k + 1): dp[n][k] += dp[n - last_summand][last_summand]

4) : , n .
5) — dp[N][1..N] .

:

, :

। Asymptotics:

।

№2:

1) . dp[n][k] — n k . , .
2) : dp[1][1] = 1 , dp[1][i] = 0 .
3) :

 dp[n][k] = dp[n - k][k] + dp[n - k][k - 1]

, . ( ) :

1 .
1 . 1 .

, :

.

, — . — , , — : .

4) : , n .

,

. , — k N ,

( 1 k ). ,

।

5) — dp[N][1..k_max] .

Asymptotics:

।

निष्कर्ष

मुख्य स्रोत प्रमुख था, और जानकारी समर कंप्यूटर स्कूल (स्कूली बच्चों के लिए), और साथ ही आंद्रेई स्टैंकेविच के सर्कल और मिखाइल ड्वोर्किन ( डारले ) के विशेष पाठ्यक्रम के व्याख्यान से मिली ।

आपका ध्यान के लिए धन्यवाद, मुझे आशा है कि यह लेख किसी के लिए उपयोगी है! यद्यपि मैं काम में आया हूँ - यह पता चला है कि एक लेख लिखना सब कुछ याद रखने का एक अच्छा तरीका है।

सब कुछ आप गतिशील प्रोग्रामिंग के बारे में जानना चाहते थे, लेकिन पूछने से डरते थे

मूल बातें

पुनर्गणना प्रक्रिया

बहुआयामी गतिशीलता

उदाहरण नंबर 1: एसएमएस की संख्या

उदाहरण 2: घोड़ा

गतिशीलता और संक्रमण मैट्रिक्स

उदाहरण संख्या 3: सवथोथ अनुक्रम

सबसिडी डायनेमिक्स

उदाहरण 4: एक स्ट्रिंग पैकिंग

उदाहरण नंबर 5: ओक्स

सबट्री डायनामिक्स

उदाहरण 6: तार्किक पेड़

सबसेट डायनामिक्स

उदाहरण नंबर 7: न्यूनतम वजन का हैमिल्टन चक्र, या यात्रा विक्रेता समस्या

प्रोफ़ाइल गतिशीलता

उदाहरण संख्या 8: डोमिनोज़ वर्चस्व

टूटी हुई प्रोफ़ाइल की गतिशीलता

उत्तर वसूली

मामूली अनुकूलन

स्मृति

समय

राज्य प्रतिस्थापन

उदाहरण संख्या 9: एक संख्या का अपघटन

№1:

№2:

निष्कर्ष

More articles: