डायनेमिक प्रोग्रामिंग: उदाहरण, सामान्य समस्याएं और समाधान

इसमें कोई संदेह नहीं है कि कोडिंग साक्षात्कार में डायनामिक प्रोग्रामिंग समस्याएं बहुत भयभीत कर सकती हैं। यहां तक ​​कि जब आप जानते हैं कि एक गतिशील प्रोग्रामिंग पद्धति का उपयोग करके एक समस्या को हल करने की आवश्यकता है, तो सीमित समय सीमा में काम कर समाधान के साथ आने में सक्षम होना एक चुनौती है।

डायनेमिक प्रोग्रामिंग समस्याओं में अच्छा होने का सबसे अच्छा तरीका है कि आप उनमें से कई के माध्यम से गुजरें। जबकि आपको हर समस्या के समाधान को याद रखने की आवश्यकता नहीं है, लेकिन किसी को लागू करने के बारे में विचार करना अच्छा है।

डायनेमिक प्रोग्रामिंग क्या है?

सीधे शब्दों में कहें, गतिशील प्रोग्रामिंग पुनरावर्ती एल्गोरिदम के लिए एक अनुकूलन विधि है, जिसका उपयोग कंप्यूटिंग या गणितीय समस्याओं को हल करने के लिए किया जाता है।

आप इसे सरल उप-समस्याओं में तोड़कर अनुकूलन समस्या को हल करने के लिए एक एल्गोरिथम तकनीक भी कह सकते हैं। डायनेमिक प्रोग्रामिंग पर आधारित एक प्रमुख सिद्धांत यह है कि किसी समस्या का इष्टतम समाधान उसकी उप-समस्याओं के समाधान पर निर्भर करता है।

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

डायनामिक रूप से प्रोग्राम किए गए समाधानों में एक बहुपद जटिलता होती है जो अन्य तकनीकों जैसे कि पुनरावृत्ति या पीछे हटने की तुलना में बहुत तेज़ चलने वाले समय का आश्वासन देती है। ज्यादातर मामलों में, गतिशील प्रोग्रामिंग समय की जटिलताओं को कम करता है, जिसे रूप में भी जाना जाता है बड़े-ओ, घातीय से बहुपद तक।

बिग-ओ नोटेशन क्या है?

आपके कोड को कुशल होने की आवश्यकता है, लेकिन आप कैसे दिखाते हैं कि कुछ कितना कुशल है? बिग-ओ के साथ!

अब जब आपको पता चल गया है कि गतिशील प्रोग्रामिंग क्या है, तो यह कुछ सामान्य समस्याओं और उनके समाधानों की जांच करने का समय है।

गतिशील प्रोग्रामिंग समस्याएँ

1. क्लेश समस्या

समस्या का विवरण

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

आपने दो पूर्णांक सरणियाँ दी हैं मान [0..n-1] तथा वज़न [0..n-1] जो क्रमशः n वस्तुओं से जुड़े मूल्यों और भार का प्रतिनिधित्व करते हैं। यह भी एक पूर्णांक है डब्ल्यू जो नॉकसैक क्षमता का प्रतिनिधित्व करता है।

यहाँ हम 0/1 की समस्या को हल कर रहे हैं, जिसका अर्थ है कि हम किसी आइटम को जोड़ना या उसे छोड़ना चुन सकते हैं।

कलन विधि

• के साथ एक दो आयामी सरणी बनाएँ एन + १ पंक्तियाँ और डब्ल्यू + १ कॉलम। एक पंक्ति संख्या एन 1 से आइटम के सेट को दर्शाता है मैं, और एक कॉलम नंबर w बैग की अधिकतम वहन क्षमता को दर्शाता है।
• पर संख्यात्मक मान [i] [जे] तक वस्तुओं के कुल मूल्य को दर्शाता है मैं एक बैग में जे का अधिकतम वजन ले जा सकता है।
• हर समन्वय पर [i] [जे] सरणी में, अधिकतम मूल्य चुनें जो हम बिना प्राप्त कर सकते हैं आइटम मैं, या अधिकतम मूल्य जो हम प्राप्त कर सकते हैं आइटम मैंजो भी बड़ा हो।
• आइटम i सहित अधिकतम प्राप्य मूल्य आइटम का योग है मैं स्वयं और अधिकतम मूल्य जो कि शूरवीरों की शेष क्षमता के साथ प्राप्त किया जा सकता है।
• इस चरण को तब तक करें जब तक आपको इसके लिए अधिकतम मूल्य न मिल जाए डब्ल्यू^वें पंक्ति।

कोड

def Findax (W, n, मान, वजन):
MaxVals = [[0 में x के लिए श्रेणी (W + 1)] में x के लिए श्रेणी (n + 1)]
मैं सीमा में (n + 1):
w में सीमा के लिए (W + 1):
अगर मैं == 0 या w == 0:
मैक्सवल्स [i] [w] = ०
एलिफ वेट [i-1] <= w:
मैक्सवल्स [i] [w] = अधिकतम (मान [i-१]
+ मैक्सवल्स [i-1] [w-weights [i-1]], 
MaxVals [i-1] [w])
अन्य:
MaxVals [i] [w] = MaxVals [i-१] [w]
वापसी मैक्सवल्स [एन] [डब्ल्यू]

2. सिक्का बदलें समस्या

समस्या का विवरण

मान लीजिए कि आपको एक संख्या दी गई है जो प्रत्येक सिक्के के मूल्यों का प्रतिनिधित्व करती है। एक विशिष्ट राशि को देखते हुए, उस राशि को बनाने के लिए आवश्यक न्यूनतम सिक्कों को खोजें।

कलन विधि

• आकार की एक सरणी प्रारंभ करें एन + १, जहां n राशि है। हर इंडेक्स की वैल्यू इनिशियलाइज़ करें मैं सरणी में राशि के बराबर होना। यह उस राशि को बनाने के लिए आवश्यक अधिकतम सिक्कों (मूल्यवर्ग 1 के सिक्कों का उपयोग करके) को दर्शाता है।
• चूंकि 0 के लिए कोई संप्रदाय नहीं है, इसलिए आधार मामले को प्रारंभ करें जहां सरणी [0] = 0.
• हर दूसरे सूचकांक के लिए मैं, हम इसमें मूल्य की तुलना करते हैं (जो शुरू में निर्धारित है एन + १) मूल्य के साथ सरणी [i-k] +1, कहां है क मै रुक जाना मैं. यह अनिवार्य रूप से हमारे द्वारा उपयोग किए जाने वाले सिक्कों की न्यूनतम संभव संख्या को खोजने के लिए i-1 तक पूरे सरणी की जांच करता है।
• अगर किसी भी मूल्य पर सरणी [i-k] + 1 मौजूदा मूल्य से कम है सरणी [i], मान को प्रतिस्थापित करें सरणी [i] एक के साथ सरणी [i-k] +1.

कोड

def coin_change (d, राशि, k):
संख्या = [0] * (राशि + 1)
j के लिए रेंज में (1, राशि + 1):
न्यूनतम = राशि
मैं सीमा में (1, k + 1):
अगर (j> = d [i]):
न्यूनतम = न्यूनतम (न्यूनतम, 1 + संख्या [j-d [i]])
संख्या [जे] = न्यूनतम
वापसी संख्या [राशि]

3. फिबोनैकी

समस्या का विवरण

फाइबोनैचि श्रृंखला पूर्णांक का एक अनुक्रम है जहां श्रृंखला में अगला पूर्णांक पिछले दो का योग है।

यह निम्नलिखित पुनरावर्ती संबंध द्वारा परिभाषित किया गया है: एफ (0) = 0, एफ (एन) = एफ (एन -1) + एफ (एन -2), कहां है एफ (एन) तब है^वें शब्द। इस समस्या में, हमें दिए गए n तक एक फाइबोनैचि अनुक्रम में सभी संख्याओं को उत्पन्न करना होगा^वें शब्द।

कलन विधि

• सबसे पहले, दिए गए पुनरावृत्ति संबंध को लागू करने के लिए एक पुनरावर्ती दृष्टिकोण का उपयोग करें।
• इस समस्या को फिर से हल करना टूटने को मजबूर करता है एफ (एन) जांच एफ (एन -1) + एफ (एन -2), और उसके बाद फ़ंक्शन को कॉल करना एफ (एन -1) तथा एफ (एन + 2) मापदंडों के रूप में। हम इसे आधार मामलों तक करते हैं जहां n = 0, या एन = 1 पहुंच गए हैं।
• अब, हम संस्मरण नामक एक तकनीक का उपयोग करते हैं। किसी सरणी में सभी फ़ंक्शन कॉल के परिणामों को संग्रहीत करें। यह सुनिश्चित करेगा कि प्रत्येक एन के लिए, एफ (एन) केवल एक बार गणना करने की आवश्यकता है।
• किसी भी बाद की गणना के लिए, इसके मूल्य को निरंतर समय में सरणी से प्राप्त किया जा सकता है।

कोड

डीईआर (एन) 
तंतुमय = [०, १] 
मैं सीमा में (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
वापसी तंतुओं [एन] 

4. सबसे लंबे समय तक बढ़ते परिणाम

समस्या का विवरण

किसी दिए गए सरणी के अंदर सबसे लंबे समय तक बढ़ने की लंबाई का पता लगाएं। सबसे लंबे समय तक बढ़ती हुई संख्या एक बढ़ते क्रम के साथ संख्या की एक सरणी के भीतर एक परिणाम है। अनुवर्ती के भीतर की संख्या अद्वितीय और आरोही क्रम में होनी चाहिए।

साथ ही, अनुक्रम की वस्तुओं को लगातार होने की आवश्यकता नहीं है।

कलन विधि

• एक पुनरावर्ती दृष्टिकोण के साथ शुरू करें, जहां आप सबसे लंबे समय तक बढ़ने के बाद के मूल्य की गणना करते हैं इंडेक्स ज़ीरो से इंडेक्स I तक, जहां मैं कम या कम के आकार के बराबर है, हर संभव सबर्रे सरणी।
• इस विधि को डायनामिक में बदलने के लिए, प्रत्येक बाद के लिए मान को संग्रहीत करने के लिए एक सरणी बनाएं। इस सरणी के सभी मानों को प्रारंभ में 0 करें।
• हर सूचकांक मैं इस सरणी आकार की एक सबसे बड़ी लंबाई के लिए सबसे लंबे समय तक बढ़ने की लंबाई से मेल खाती है मैं.
• अब, हर पुनरावर्ती कॉल के लिए findLIS (गिरफ्तार, n), जाँचें एन^वें सरणी का सूचकांक। यदि यह मान 0 है, तो पहले चरण में विधि का उपयोग करके मान की गणना करें और इसे स्टोर करें एन^वें सूचकांक।
• अंत में, सरणी से अधिकतम मान लौटाएं। यह किसी दिए गए आकार के सबसे लंबे समय तक बढ़ने की लंबाई है एन.

कोड

def findLIS (myArray):
n = लेन (myArray)
लिस = [०] * एन
मैं सीमा में (1, n):
j के लिए रेंज में (0, i):
अगर myArray [i]> myArray [j] और lis [i] lis [i] = lis [j] +1
मैक्सवेल = ०
i for रेंज (n):
maxVal = अधिकतम (maxVal, lis [i])
अधिकतम वापसी

डायनेमिक प्रोग्रामिंग समस्याओं का समाधान

अब जब आप सबसे लोकप्रिय गतिशील प्रोग्रामिंग समस्याओं में से कुछ के माध्यम से चले गए हैं, तो अपने आप से समाधान को लागू करने की कोशिश करने का समय है। यदि आप अटक गए हैं, तो आप हमेशा वापस आ सकते हैं और ऊपर प्रत्येक समस्या के लिए एल्गोरिथ्म अनुभाग का संदर्भ ले सकते हैं।

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

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

9 सर्वश्रेष्ठ कोड-साथ YouTube चैनल प्रोग्रामिंग सीखने के लिए

कोडिंग शुरू करने के लिए तैयार हैं? ये YouTube चैनल गेम, ऐप, वेब और अन्य विकास में आरंभ करने का एक शानदार तरीका है।

लेखक के बारे में