डायनामिक प्रोग्रामिङ (DP) ले overlapping subproblems र optimal substructure भएका समस्याहरू समाधान गर्छ प्रत्येक subproblem एक पटक गणना गरेर र नतिजा पुनः प्रयोग गरेर। दुई शैलीहरू हुन् memoization (top-down) र tabulation (bottom-up)।
Naive recursion एउटै subproblems लाई exponentially पुनः गणना गर्छ। DP ले यसलाई cache गर्छ, exponential काम लाई polynomial मा collapse गर्दै।
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]
| Memoization | Tabulation | |
|---|---|---|
| Direction | top-down recursion | bottom-up iteration |
| Computes | केवल आवश्यक states | सबै states |
| Risk | stack overflow | कुनै पनि छैन |
| Space | काट्न सकिन्छ | प्रायः O(1) rows मा घटाउन सकिन्छ |
Fibonacci: O(2ⁿ) naive बाट O(n) time, O(n) (वा O(1)) space सम्म।
DP प्रयोग गर्नुहोस् जब subproblems overlap हुन्। state र recurrence सावधानीपूर्वक परिभाषित गर्नुहोस् — यो कठिन भाग हो। यदि subproblems overlap गर्दैनन्, साधारण divide-and-conquer पर्याप्त छ।
DP ले intractable exponential समस्याहरू — shortest paths, edit distance, knapsack — लाई दक्ष गर्छ।
state र recurrence पहिचान गर्ने कौशल algorithm interviews मा सबैभन्दा मूल्यवान छ।
यो diff tools देखि bioinformatics sequence alignment सम्म real systems मा आधारभूत छ।