Dinaminis programavimas (DP) sprendžia problemas su persidengusiais pobroblėmais ir optimaliu postruktūru, apskaičiavus kiekvieną pobroblėmą vieną kartą ir iš naujo naudojant rezultatą. Du stiliai yra memoization (nuo viršaus į apačią) ir tabulation (nuo apačios į viršų).
Naivi rekursija iš naujo apskaičiuoja tuos pačius pobroblėmus eksponentiškai. DP juos talpina, sumažindama eksponentinį darbą į polinomą.
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 | |
|---|---|---|
| Kryptis | nuo viršaus į apačią rekursija | nuo apačios į viršų iteracija |
| Apskaičiuoja | tik reikalingos būsenos | visos būsenos |
| Rizika | stack overflow | nėra |
| Vieta | gali būti mažinta | dažnai sumažiinama iki O(1) eilučių |
Fibonačis: iš O(2ⁿ) naiviausios į O(n) laiką, O(n) (arba O(1)) vietą.
Naudokite DP, kai pobroblėmės persidena. Kruopščiai apibrėžkite būseną ir pasikartojimą — tai sudėtinga dalis. Jei pobroblėmės nesidena, paprastas dalyti-ir-valdyti yra pakankamas.
DP paverčia neišsprendžiamas eksponentines problemas — trumpiausius kelius, redagavimo nuotolį, kuprinę — efektyviai sprendžiamomis.
Būsenos ir pasikartojimo nustatymo įgūdis yra vienas iš labiausiai vertintų algoritmo pokalbių.
Jis yra realiųjų sistemų, pradedant skirtumų įrankiais, baigiant bioinformatikos sekų lygiavimais, pagrindas.