डायनामिक प्रोग्रामिंग (DP) ओव्हरलॅपिंग सबप्रॉब्लेम्स आणि ऑप्टिमल सबस्ट्रक्चर असलेल्या समस्या सोडवते, प्रत्येक सबप्रॉब्लेम एकदा मोजून आणि परिणाम पुन्हा वापरून. दोन शैली आहेत memoization (top-down) आणि tabulation (bottom-up).
निरपेक्ष रिकर्सन समान सबप्रॉब्लेम्सची घातांकीय पुनरावृत्ती करते. 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]
| Memoization | Tabulation | |
|---|---|---|
| दिशा | top-down रिकर्सन | bottom-up इटरेशन |
| मोजते | फक्त आवश्यक स्थिती | सर्व स्थिती |
| धोका | stack overflow | काहीच नाही |
| जागा | कमी केली जाऊ शकते | बहुधा O(1) पंक्तीपर्यंत कमी केली जाऊ शकते |
फिबोनाची: O(2ⁿ) निरपेक्षातून O(n) वेळ, O(n) (किंवा O(1)) जागा.
जेव्हा सबप्रॉब्लेम्स ओव्हरलॅप करतात तेव्हा DP वापरा. स्थिती आणि पुनरावृत्ती सावधानीपूर्वक परिभाषित करा — हा अवघड भाग आहे. जर सबप्रॉब्लेम्स ओव्हरलॅप न करतात, तर सादा divide-and-conquer पुरेसे आहे.
DP अव्यवहार्य घातांकीय समस्या — सर्वात लहान मार्ग, संपादन अंतर, नॅपस्यूक — कार्यक्षम बनवते.
स्थिती आणि पुनरावृत्ती ओळखण्याचे कौशल्य अल्गोरिदम मुलाखतीत सर्वाधिक मूल्यवान आहे.
हे diff साधनांपासून बायोइनफॉर्मेटिक्स अनुक्रम संरेखनापर्यंत वास्तविक प्रणाली काम करते.