ડાયનેમિક પ્રોગ્રામિંગ (DP) એ સમસ્યાઓને અતિક્રમણશીલ સબપ્રોબ્લેમ્સ અને શ્રેષ્ઠ સબસ્ટ્રક્ચર સાથે હલ કરે છે દરેક સબપ્રોબ્લેમને એક વાર ગણતરી કરીને અને પરિણામ પુનરાবૃત્તિ કરીને. બે શૈલીઓ મેમોરાઇઝેશન (top-down) અને ટેબ્યુલેશન (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]
| મેમોરાઇઝેશન | ટેબ્યુલેશન | |
|---|---|---|
| દિશા | top-down પુનરાવર્તન | bottom-up પુનરાવર્તન |
| ગણતરી કરે | શરૂરૂ આવશ્યક સ્થિતિઓ માત્ર | બધી સ્થિતિઓ |
| જોખમ | સ્ટેક ઓવરફ્લો | કોઈ નહીં |
| સ્થાન | ઘટાડી શકાય | ઘણીવાર O(1) હરોળે ઘટાડી શકાય |
ફિબોનાકી: O(2ⁿ) નિરાધાર થી O(n) સમય, O(n) (અથવા O(1)) સ્થાન.
DP વાપરો જ્યારે સબપ્રોબ્લેમ્સ અતિક્રમણ થાય. સ્થિતિ અને પુનરાવર્તન સાવધાનીથી વ્યાખ્યાયિત કરો — તે મુશ્કેલ ભાગ છે. જો સબપ્રોબ્લેમ્સ અતિક્રમણ ન થાય, તો સાદો divide-and-conquer પર્યાપ્ત છે.
DP અસંભવ ઘાતાંકીય સમસ્યાઓને રૂપાંતરિત કરે છે — સૌથી ટૂંકા પથ, સંપાદન અંતર, નેપસેક — કાર્યક્ષમ માં.
સ્થિતિ અને પુનરાવર્તન ઓળખવાની કુશળતા એલ્ગોરિધમ ઇન્ટરવ્યુમાં સૌથી વધુ માંગવામાં આવે છે.
તે વાસ્તવિક સિસ્ટમ્સને અંતર્ગત કરે છે diff સાધનોથી બાયોઇનફોર્મેટિક્સ સિક્વન્સ સંરેખણ સુધી.