सीधा रिकर्शन धीमा क्यों हो सकता है
फ़िबोनाची नियम: fib(n) = fib(n − 1) + fib(n − 2), जहाँ fib(0) = 0 और fib(1) = 1। सीधे रिकर्शन में हर पुकार दो और पुकारें करती है। पुकारें लगभग 1.6n की तरह बढ़ती हैं: fib(30) के लिए दस लाख से ज़्यादा पुकारें। यह घातांकी समय है।
बर्बादी इसलिए कि वही उपसमस्या बार-बार हल होती है।
DP की दो शर्तें
- अतिव्यापी उपसमस्याएँ: वही छोटी समस्या कई बार आती है।
- इष्टतम उपसंरचना: बड़ी समस्या का सबसे अच्छा उत्तर छोटी समस्याओं के सबसे अच्छे उत्तरों से बनता है।
DP बनाने के क़दम: (1) अवस्था तय करो (तालिका का एक खाना क्या दर्शाता है), (2) पुनरावृत्ति संबंध लिखो (खाना छोटे खानों से कैसे बनता है), (3) आधार स्थितियाँ रखो, (4) भरने का क्रम चुनो, (5) उत्तर पढ़ो।
ऊपर से नीचे (मेमोइज़ेशन) और नीचे से ऊपर (टेबुलेशन)
मेमोइज़ेशन (ऊपर से नीचे)
रिकर्शन रखो पर उत्तर डिक्शनरी या ऐरे में याद रखो।
memo = {}
def fib(n):
if n < 2:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]टेबुलेशन (नीचे से ऊपर)
लूप से सबसे छोटी स्थिति से ऊपर की ओर ऐरे भरो।
def fib(n):
F = [0] * (n + 1)
if n > 0: F[1] = 1
for i in range(2, n + 1):
F[i] = F[i - 1] + F[i - 2]
return F[n]दोनों घातांकी की जगह O(n) समय लेते हैं। टेबुलेशन में कॉल स्टैक नहीं, इसलिए ओवरफ़्लो नहीं। तालिका में सिर्फ़ आख़िरी दो मान रखकर मेमोरी O(1) भी हो सकती है।
अन्य प्रोग्रामिंग विधियाँ: लालची, बैकट्रैकिंग, विभाजन और विजय
- लालची (greedy): हर क़दम पर वही चुनो जो अभी सबसे अच्छा लगे, कभी पीछे मत लौटो। तेज़, पर केवल कुछ समस्याओं में सही (जैसे 1, 2, 5, 10 के सिक्कों से छुट्टा देना, या न टकराने वाली सबसे ज़्यादा गतिविधियाँ चुनना)। {1, 3, 4} और 6 के लिए लालची 3 सिक्के देता है, जबकि सबसे अच्छा 2 है।
- विभाजन और विजय: स्वतंत्र हिस्सों में बाँटो, हर एक हल करो, जोड़ो (मर्ज सॉर्ट, बाइनरी सर्च)। हिस्से दोहराते नहीं, तालिका की ज़रूरत नहीं।
- बैकट्रैकिंग: हल क़दम-दर-क़दम बनाओ और जो क़दम काम न करे उसे वापस लो (N-क्वीन, सुडोकू, सारे उपसमुच्चय)। बहुत विकल्प खोजता है, धीमा हो सकता है।
- DP: विभाजन और विजय जैसा, पर हिस्से दोहराते हैं, इसलिए उत्तर सहेजो।
DP से सिक्का समस्या
def min_coins(coins, amount):
INF = float('inf')
best = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1
return best[amount]समय O(रक़म × सिक्कों की संख्या)।
करके देखिए: सीढ़ी के रास्ते गिनिए
आप सीढ़ी पर एक बार में 1 या 2 सीढ़ी चढ़ते हैं। सीढ़ी 6 तक कितने तरीक़े? तालिका बनाइए: ways[0] = 1, ways[1] = 1, ways[i] = ways[i − 1] + ways[i − 2]। काग़ज़ पर भरिए (उत्तर: 13)। यह फिर फ़िबोनाची पैटर्न है। 3D के आख़िरी क़दम में तालिका भरकर जाँचिए, फिर पायथन में लिखिए।
मुख्य सूत्र और परिभाषाएँ
- [object Object]
- [object Object]
- [object Object]
- [object Object]
हल किए गए उदाहरण
1. फ़िबोनाची के लिए F[0..7] तालिका भरिए।
0, 1, 1, 2, 3, 5, 8, 13। हर मान पिछले दो का जोड़।
2. fib(5) के लिए सीधा रिकर्शन कितनी पुकारें करता है?
Calls(0) = Calls(1) = 1। Calls(2) = 3, Calls(3) = 5, Calls(4) = 9, Calls(5) = 1 + 9 + 5 = 15।
3. मेमोइज़ेशन के साथ fib(5) की पुकारें?
5 से 2 तक हर n पहली बार 2 पुकारें करता है; कुल 2 × 5 − 1 = 9।
4. DP से {1, 3, 4} सिक्कों से 6 के लिए सबसे कम सिक्के।
best[0..6] = 0, 1, 2, 1, 1, 2, 2। best[6] = 1 + min(best[5], best[3], best[2]) = 1 + 1 = 2 (3 + 3)।
5. सीढ़ी: 1 या 2 क़दम, सीढ़ी 5 तक कितने तरीक़े?
सीढ़ी 0..5 के लिए ways = 1, 1, 2, 3, 5, 8, इसलिए 8 तरीक़े।
6. ग्रिड रास्ते: 3 × 3 खानों की ग्रिड में केवल दाएँ या नीचे चलकर कोने से कोने तक कितने रास्ते?
paths[i][j] = paths[i−1][j] + paths[i][j−1], पहली पंक्ति और स्तंभ = 1। पंक्तियाँ: 1 1 1 / 1 2 3 / 1 3 6। उत्तर 6।
आम गलतियाँ
- जहाँ उपसमस्याएँ दोहराती नहीं वहाँ DP लगाना (सीधा विभाजन और विजय काफ़ी है)।
- आधार स्थितियाँ भूल जाना, जिससे तालिका ग़लत मानों से शुरू होती है।
- तालिका ग़लत क्रम में भरना: कोई खाना बनने से पहले पढ़ लिया जाता है।
- बिना जाँचे लालची पर भरोसा: {1, 3, 4} और 6 के लिए वह चूक जाता है।