DP i hladový přístup vyžadují optimální podstrukturu. Rozdíl: hladový také vyžaduje vlastnost hladové volby (lokální optimum je globálně optimální), zatímco DP je potřebný, když musíte zvážit více možností a překrývající se dílčí problémy.
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
Hladový přístup se zavazuje jednou volbou; DP zkoumá všechny a zachovává tu nejlepší.
Hladový přístup je obvykle O(n log n); DP vyměňuje více času/prostoru (často O(n·m)) za správnost.
Verejné používání hladového přístupu bez prokázání jeho vlastnosti dává špatné odpovědi, které projdou malými testy. Pokud si nejste jistí, použijte DP nebo ověřte hladový přístup hrubou silou.
Volba hladového přístupu, když je platný, ušetří obrovský čas; volba, když není, vede k tichým chybám.
Vědět, který paradigma vyhovuje — a být schopen jej prokázat — je rozlišení na úrovni senior.
Prevenci před přeingenerováním pomocí DP a nedostatečným dodáním s nesprávnou hladovou volbou.
Knihovna IT otázek k pohovoru s podrobnými odpověďmi — od Junior po Senior.
Přispět