Dynamic programming (DP) solvi problemi b'overlapping subproblems u optimal substructure billi tikkomputa kull problem subwa darba waħda u terġa tużza r-riżultat. Iż-żewġ istili huma memoization (top-down) u tabulation (bottom-up).
Rikursjoni ingennwa tirrikomputà l-istess subproblems b'mod esponenzjali. DP jipponjah lhom, iduċċ ix-xogħol esponenzjali f'polinomjali.
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| Memoization | Tabulation | |
|---|---|---|
| Direzzjoni | rikursjoni top-down | iċċiklu bottom-up |
| Tikkomputa | biss l-istati meħtieġa | l-istati kollha |
| Riskju | stack overflow | ebda ħadd |
| Spazju | jista' jitqass | ħafna drabi jista' jitnaqqas għal O(1) ringieli |
Fibonacci: minn O(2ⁿ) ingennwa għal O(n) ħin, O(n) (jew O(1)) spazju.
Uża DP meta subproblems jikkoinċidu. Iddefinisċi l-istat u r-rikorrenza b'attenzjoni — dik hija l-parti diffiċli. Jekk subproblems ma jikkoinċidux, divide-and-conquer sempliċi huwa biżżejjed.
DP ibiddel problemi esponenzjali li ma jistgħux jitwettqu — l-aqsar mogħdijiet, distanza ta' editur, knapsack — f'dawk efficienti.
Il-kapaċità li tidentifika l-istat u r-rikorrenza hija waħda mill-aktar valutata fil-interviews ta' algoritmi.
Jiddendendi mis-sistemi reali minn tools diff sa alignment ta' sekwenzi ta' bioinformatics.