Kedua-dua DP dan greedy memerlukan optimal substructure. Perbezaannya: greedy juga memerlukan greedy-choice property (optimum tempatan adalah optimum sejagat), manakala DP diperlukan apabila anda mesti mempertimbangkan pelbagai pilihan dan submasalah yang bertindih.
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 komited kepada satu pilihan; DP meneroka semua dan menyimpan yang terbaik.
Greedy biasanya O(n log n); DP berkompromi dengan lebih banyak masa/ruang (selalunya O(n·m)) demi kebetulan.
Menggunakan greedy tanpa membuktikan sifatnya memberi jawapan salah yang lulus ujian kecil. Apabila ragu, gunakan DP atau sahkan greedy terhadap brute force.
Memilih greedy apabila ia sah menjimatkan masa yang amat banyak; memilihnya apabila ia tidak sah menghasilkan pepijat senyap.
Mengetahui paradigma mana yang sesuai — dan mampu membuktikannya — ialah perbezaan peringkat senior.
Ia menghalang kedua-dua over-engineering dengan DP dan kurang-penyampaian dengan pilihan greedy yang tidak kukuh.