डायनॅमिक प्रोग्रामिंग बेसिक्स


अडचण पातळी सोपे
वारंवार विचारले इन्फोसिस एमक्यू
डायनॅमिक प्रोग्रामिंग सिद्धांत

डायनॅमिक प्रोग्रामिंग मूलभूत गोष्टींमध्ये, आम्ही डीपीची मूलभूत माहिती आणि त्याचे लोभी पध्दती, विभाजन आणि विजय आणि पुनरावर्तन यापासून वेगळे करतो.

डायनॅमिक प्रोग्रामिंग ही पुनरावृत्ती आणि विभाजन आणि विजय या सारख्या दृष्टीकोनाचा आहे. हे समस्येला सबप्रोब्लम्समध्ये विभाजित करते. परंतु या उपप्रश्ल्या स्वतंत्रपणे विभाजन आणि विजय आणि पुनरावृत्तीसारखे सोडवण्याऐवजी आधीच्या सबप्रोब्लम्सच्या परिणामाचा वापर समान संगणनासाठी करतात ज्याला आच्छादित समस्या देखील म्हटले जाते.

त्याचा उपयोग प्रोग्राम्सच्या ऑप्टिमायझेशनसाठी होतो. पूर्वीचे गणित निकाल वापरल्यामुळे, त्याच्या घातांकीय वेळेची जटिलता वापरुन बहुपदीपर्यंत कमी करता येते. उदाहरणार्थ - कुरूप क्रमांकांच्या रिकर्सिव्ह सोल्यूशनची वेळ गुंतागुंतीची असते आणि डीपी सोल्यूशन रेषात्मक असते.

डीपीच्या काही मूलभूत समस्या

  • कुरुप संख्या समस्या
  • नाणे बदल
  • फिबोनाची संख्या
  • बेल क्रमांक समस्या
  • हॅनाइचा टॉवर
  • बेल क्रमांक
  • नॅप्सॅक समस्या

डायनॅमिक प्रोग्रामिंग (डीपी) वि लोभी पद्धत

डीपीमध्ये प्रत्येक चरण इष्टतम सोल्यूशन प्राप्त करण्यासाठी वर्तमान तसेच मागील उपायांचा विचार करुन समाधानाचे मूल्यांकन करतो. तथापि, लोभी अल्गोरिदममध्ये आम्ही फक्त सद्य परिस्थितीचा विचार करुन सर्वोत्तम पर्याय निवडतो.

जरी लोभी पद्धती सामान्यत: डीपीपेक्षा वेगवान असतात आणि मेमरी कार्यक्षम देखील असतात कारण भविष्यात वापरण्यासाठी पूर्वीची गणना केलेली मूल्ये ती साठवत नाहीत, परंतु ते चांगल्या समाधानाचे आश्वासन देत नाही.

डायनामिक प्रोग्रामिंग (डीपी) वि डिवाइड आणि कॉन्कर मेथड

विभाजित आणि विजय मध्ये आम्ही एखाद्या समस्येस सबप्रोब्लम्समध्ये विभाजित करतो आणि प्रत्येक उपप्रश्ले स्वतंत्रपणे सोडवितो. तथापि, स्वतंत्रपणे समस्या सोडविण्याऐवजी डीपीमध्ये आम्ही नवीन गणनेसाठी आधीचे निकाल वापरतो. दुसर्‍या शब्दांत सांगायचे तर आम्ही डिव्हिड अँड कॉन्क्वेअर + मेमोइझेशन = टॉप-डाऊन डायनॅमिक अ‍ॅप्रोच म्हणतो.

(स्मृतीकरण म्हणजे समान गणिते पुन्हा पुन्हा पुन्हा टाळण्यासाठी पूर्वीचे गणित निकाल सामान्यत: हॅश-मॅपमध्ये संग्रहित करण्याच्या तंत्राचा संदर्भ देते.)

डायनॅमिक प्रोग्रामिंग (डीपी) वि रिकर्सन पद्धत

डीपी पूर्वीची गणना केलेली निराकरणे पुन्हा वापरण्यापासून टाळण्यासाठी भविष्यात पुन्हा आवश्यक असल्यास म्हणून वापरतात. तथापि, पुनरावृत्तीमध्ये, पुन्हा गणना करण्याची शक्यता आहे जी मूल्ये साठवत नसल्यामुळे अनावश्यक आहे.

रिकर्सनमुळे समस्यांची पुन्हा पुन्हा मोजणी होते कारण अशा परिस्थितीत डीपी सोल्यूशनपेक्षा पुनरावृत्तीची वेळ जटिलता नेहमीच जास्त असते.

या लेखात, आम्ही याबद्दल कव्हर केले डायनॅमिक प्रोग्रामिंग मुलभूत गोष्टी. पुढील लेखात आम्ही डीपीवरील काही मूलभूत समस्या पाहू.

संदर्भ मुलाखत प्रश्न