Sowohl DP als auch Greedy benötigen optimale Substruktur. Der Unterschied: Greedy erfordert zusätzlich die Greedy-Choice-Eigenschaft (ein lokales Optimum ist global optimal), während DP notwendig ist, wenn Sie mehrere Auswahlmöglichkeiten und überlappende Teilprobleme berücksichtigen müssen.
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 verpflichtet sich auf eine Wahl; DP erkundet alle und behält die beste.
Greedy ist normalerweise O(n log n); DP tauscht mehr Zeit/Speicher (oft O(n·m)) gegen Korrektheit.
Die Verwendung von Greedy ohne Beweis seiner Eigenschaft führt zu falschen Antworten, die kleine Tests bestehen. Im Zweifelsfall verwenden Sie DP oder überprüfen Sie Greedy gegen Brute Force.
Greedy auszuwählen, wenn es gültig ist, spart enorme Zeit; es auszuwählen, wenn es nicht gültig ist, führt zu stillen Fehlern.
Zu wissen, welches Paradigma passt — und es beweisen zu können — ist eine Unterscheidung auf Senior-Ebene.
Es verhindert sowohl Überentwicklung mit DP als auch Unterlieferung mit einer unsicheren Greedy-Wahl.