DP மற்றும் பேராசையான இரண்டும் உகந்த உபகணன அமைப்பு தேவை. வேறுபாடு: பேராசையான பேராசையான-தேர்வு சম்பத்தை (உள்ளூர் உச்சம் உலகளாவிய உச்சம்) கூட தேவை, அதே சமயம் DP நீ பல தேர்வுகளை மற்றும் ஒன்றுபடும் உபப்பிரச்சனை பற்றி சிந்திக்க வேண்டியதாக தேவை.
Optimal substructure? -- both need this
+ greedy-choice property holds? -> GREEDY (fast, one pass of choices)
+ must compare many sub-solutions / they overlap? -> DYNAMIC PROGRAMMING
# Greedy FAILS for coins {1,3,4}, amount 6 -> 4+1+1 (3 coins)
# DP finds the true optimum: 3+3 (2 coins)
def min_coins(amount, coins):
INF = float('inf')
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1) # try every coin
return dp[amount]
min_coins(6, [1, 3, 4]) # -> 2
பேராசையான ஒரு தேர்வுக்கு தன்னை பிணைக்கிறது; DP அனைத்தையும் ஆராயுகிறது மற்றும் சிறந்ததை வைத்துக்கொள்கிறது.
பேராசையான பொதுவாக O(n log n); DP மேல் நேரம்/இடம் மாற்றியமைக்கிறது (பொதுவாக O(n·m)) சரிசெய்து.
பேராசையானை அதன் சம்பத்தை நிரூபிக்காமல் பயன்படுத்துதல் தவறான பதில் கொடுக்கிறது சிறிய சோதனை கடந்து. உனக்கு சந்தேகம் இருந்தால், DP பற்றி போ அல்லது பேராசையானை வெறும் சக்தியை விரோதி ஆராயுங்கள்.
பேராசையான பொருந்தும் போது தேர்வு கோடி நேரம் சேமிக்கிறது; அது பொருந்தாத போது தேர்வு மூல தவறுகள் உற்பத்தி செய்கிறது.
எந்த பாரம்பரியம் பொருந்துகிறது என்று தெரிதல் — மற்றும் அதை நிரூபிக்க முடியுதல் — உயர்ந்த-நிலை வேறுபாடு.
இது DP உடன் அதிக பொறியியல் மற்றும் ஒரு நம்பிக்கை இல்லாத பேராசையான தேர்வு உடன் கீழ்-வழங்கல் தடுக்கிறது.