डायनामिक प्रोग्रामिंग (DP) ओवरलैपिंग सबप्रॉब्लेम्स और इष्टतम सबस्ट्रक्चर वाली समस्याओं को हल करता है प्रत्येक सबप्रॉब्लम को एक बार कंप्यूट करके और परिणाम का पुन: उपयोग करके। दो शैलियाँ मेमोइजेशन (top-down) और टेबुलेशन (bottom-up) हैं।
Naive recursion समान सबप्रॉब्लम्स को घातीय रूप से दोबारा कंप्यूट करता है। DP उन्हें कैश करता है, घातीय कार्य को बहुपद में बदल देता है।
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| मेमोइजेशन | टेबुलेशन | |
|---|---|---|
| दिशा | top-down recursion | bottom-up iteration |
| गणना करता है | केवल आवश्यक states | सभी states |
| जोखिम | stack overflow | कोई नहीं |
| स्पेस | कम किया जा सकता है | अक्सर O(1) पंक्तियों तक कम किया जा सकता है |
Fibonacci: O(2ⁿ) naive से O(n) समय, O(n) (या O(1)) स्पेस।
DP का उपयोग करें जब सबप्रॉब्लम्स ओवरलैप करें। स्टेट और recurrence को सावधानी से परिभाषित करें — यही कठिन हिस्सा है। अगर सबप्रॉब्लम्स ओवरलैप नहीं करते, तो सामान्य divide-and-conquer काफी है।
DP कठिन घातीय समस्याओं को — shortest paths, edit distance, knapsack — efficient में बदल देता है।
State और recurrence की पहचान करने का कौशल एल्गोरिदम साक्षात्कार में सबसे मूल्यवान है।
यह diff tools से लेकर bioinformatics sequence alignment तक वास्तविक सिस्टम को रेखांकित करता है।