गतिशील प्रोग्रामिंग और मैट्रिस का उपयोग

Question

मैं हमेशा इस बारे में उलझन में हूं कि किसी समस्या को हल करने के लिए गतिशील प्रोग्रामिंग मैट्रिक्स का उपयोग कैसे करता है। मैं मोटे तौर पर समझता हूं कि मैट्रिक्स का उपयोग पिछले उपप्रोबम्स से परिणामों को संग्रहीत करने के लिए किया जाता है, ताकि इसका उपयोग बाद में बड़ी समस्या के गणना में किया जा सके।

लेकिन, मैट्रिक्स के आयाम को कैसे निर्धारित करता है, और हम कैसे जानते हैं कि मैट्रिक्स की प्रत्येक पंक्ति/कॉलम का प्रतिनिधित्व करना चाहिए? यानी, मैट्रिक्स बनाने की एक सामान्य प्रक्रिया की तरह है?

उदाहरण के लिए, यदि हम मूल्य c1, c2, .... cn के सिक्कों का उपयोग करके एस राशि के लिए परिवर्तन करने में रुचि रखते हैं, तो मैट्रिक्स का आयाम क्या होना चाहिए, और प्रत्येक कॉलम/पंक्ति क्या होनी चाहिए प्रतिनिधित्व करते हैं?

कोई भी दिशात्मक मार्गदर्शन मदद करेगा। धन्यवाद!

Answer 1

डीपी समस्याओं में से कुछ प्रकार के लिए असहज कदम:

1. पुनरावर्ती समाधान

2. पुनरावर्ती कॉल में से कुछ मध्यवर्ती परिणाम बार-बार की गणना कर रहे हैं खोजें - उन्हें और उपयोग याद - के साथ एक मेज का निर्माण उपयुक्त आयाम - यह ज्ञापन

3. यह तालिका आमतौर पर सेल से अंतिम (परिणाम) - सेल द्वारा सेल, पंक्ति से पंक्ति और इतने पर ... से भरने से भरा जा सकता है ...

परिवर्तन समस्या के लिए:

1. एफ (रों) = एफ (रों-C1) + F (रों-C2) + ...

पूर्ण पुनरावर्ती समाधान विस्तृत और निर्धारित करने के लिए प्रयास करें क्या तालिका मध्यवर्ती परिणाम

Answer 2

एक डी पी समाधान द्वारा इस्तेमाल किया एक सरणी लगभग हमेशा समस्या का राज्य अंतरिक्ष के आयामों पर आधारित है स्टोर करने के लिए की जरूरत है - वह यह है कि इसके मापदंडों से प्रत्येक के लिए मान्य मान

उदाहरण

fib[i+2] = fib[i+1] + fib[i] 

लिए, एक ही

रूप

def fib(i): 
    return fib(i-1)+fib(i-2] 

आप अपने पुनरावर्ती कार्यों

def fib(i): 
    if(memo[i] == null) 
     memo[i] = fib(i-1)+fib(i-2) 
    return memo[i] 

अपने पुनरावर्ती क्रिया कश्मीर पैरामीटर है, तो में Memoization को लागू करने से इस अधिक स्पष्ट कर सकते हैं है आपको शायद के-आयामी मैट्रिक्स की आवश्यकता होगी।

Answer 3

यह अध्याय यह बहुत अच्छी तरह से बताता है: http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf पृष्ठ 178 पर यह उप-समस्याओं की पहचान करने के लिए कुछ दृष्टिकोण देता है जो आपको गतिशील प्रोग्रामिंग लागू करने की अनुमति देते हैं।