డైనమిక్ ప్రోగ్రామింగ్ (DP) అతిపెక్క సబ్ప్రాబ్లెమ్ల మరియు సరైన సబ్స్ట్రక్చర్ ఉన్న సమస్యలను సాధిస్తుంది, ప్రతి సబ్ప్రాబ్లెమ్ను ఒకసారి లెక్కించి, ఫలితాన్ని మళ్లీ ఉపయోగించుకోవడ ద్వారా. రెండు శైలులు మెమోయిజేషన్ (టాప్-డౌన్) మరియు టాబులేషన్ (బాటమ్-అప్) వీటిలో ఉంటాయి.
సరళ పునరావృత్తి ఒకే సబ్ప్రాబ్లెమ్లను ఎక్స్పోనెన్షియల్గా మళ్లీ లెక్కిస్తుంది. 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]
| | మెమోయిజేషన్ | టాబులేషన్ | |---|------------|------------|| | దిశ | టాప్-డౌన్ పునరావృత్తి | బాటమ్-అప్ పునరుక్తి | | లెక్కిస్తుంది | అవసరమైన స్థితులు మాత్రమే | అన్ని స్థితులు | | ఖతరం | స్టాక్ ఓవర్ఫ్లో | లేదు | | స్థలం | కత్తిరించవచ్చు | తరచుగా O(1) వరుసలకు తగ్గించవచ్చు |
ఫిబోనాచ్చీ: O(2ⁿ) సరళ నుండి O(n) సమయం, O(n) (లేదా O(1)) స్థలం.
సబ్ప్రాబ్లెమ్లు అతిపెక్క ఉన్నప్పుడు DP ఉపయోగించండి. స్థితి మరియు పునరావృత్తిని జాగ్రత్తగా నిర్వచించండి — ఇది కష్టమైన భాగం. సబ్ప్రాబ్లెమ్లు అతిపెక్క లేకపోతే, సాధారణ విభజన-మరియు-జయించుటలు సరిపోతాయి.
DP ఘర్షణీయ ఎక్స్పోనెన్షియల్ సమస్యలను — చిన్న మార్గాలు, సవరణ దూరం, నగదు కిటికీ — సమర్థవంతమైనవిగా చేస్తుంది.
స్థితి మరియు పునరావృత్తిని గుర్తించే నైపుణ్యం అల్గోరిథం ఇంటర్వ్యూలలో ఎక్కువ విలువైనది.
ఇది diff సాధనాల నుండి బయోఇన్ఫార్మేటిక్స్ సీక్వెన్స్ సంరేఖణ వరకు నిజమైన వ్యవస్థల ఆధారం.