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