Dynaaminen ohjelmointi (DP) ratkaisee ongelmia, joissa on overlapping subproblems ja optimal substructure, laskemalla jokaisen aliongelman kerran ja käyttäen tulosta uudelleen. Kaksi tyyliä ovat memoization (top-down) ja tabulation (bottom-up).
Naivi rekursio laskee samat aliongelmat uudelleen eksponentiaalisesti. DP tallentaa ne välimuistiin, muuttaen eksponentiaalisen työn polynomiaalista.
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 | |
|---|---|---|
| Suunta | top-down rekursio | bottom-up iteraatio |
| Laskee | vain tarvittavat tilat | kaikki tilat |
| Riski | stack overflow | ei riskiä |
| Tila | voidaan lyhentää | usein pelkistettävissä O(1) riveihin |
Fibonacci: O(2ⁿ) naiivista O(n) aikaan, O(n) (tai O(1)) tilaan.
Käytä DP:tä, kun aliongelmat päällekkäisiä. Määritä tila ja rekursio huolellisesti — se on vaikea osa. Jos aliongelmat eivät ole päällekkäisiä, tavallinen divide-and-conquer riittää.
DP muuttaa ratkaistavat eksponentiaaliset ongelmat — lyhyimmät polut, edit distance, knapsack — tehokkaiksi.
Taito tilan ja rekursion tunnistamiseen on yksi arvostetuimmista algoritmi-haastatteluissa.
Se on perustana todellisille järjestelmille diff-työkaluista bioinformatiikan sekvenssien tasaukseen.