Both DP and greedy need optimal substructure. The difference: greedy also requires the greedy-choice property (a local optimum is globally optimal), while DP is needed when you must consider multiple choices and overlapping subproblems.
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
Greedy commits to one choice; DP explores all and keeps the best.
Greedy is usually O(n log n); DP trades more time/space (often O(n·m)) for correctness.
Using greedy without proving its property gives wrong answers that pass small tests. When in doubt, reach for DP or verify greedy against brute force.
जब यह मान्य हो तो लालची को चुनना बहुत समय बचाता है; जब यह न हो तो इसे चुनना मूक बग पैदा करता है।
कौन सी paradigm फिट बैठती है यह जानना — और इसे साबित करने में सक्षम होना — एक senior-स्तरीय अंतर है।
यह DP के साथ over-engineering और unsound लालची चुनाव के साथ under-delivering दोनों को रोकता है।
विस्तृत उत्तरों के साथ IT इंटरव्यू प्रश्नों की एक लाइब्रेरी — जूनियर से सीनियर तक।
दान करें