Dynamic programming (DP) yana warware matsaloli tare da overlapping subproblems da optimal substructure ta hanyar ƙididdige kowane matsala ta ɗaya a lokaci gida da sake amfani da sakamakon. Duwan saituka (saituka) gida memoization (top-down) da tabulation (bottom-up).
Sauƙin recursion yana sake ƙididdige matsaloli gida sau da yawa. DP na ajiye su a cache, sauya aikin exponential zuwa polynomial.
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 | |
|---|---|---|
| Alkibla | top-down recursion | bottom-up iteration |
| Ƙididdiga | kawai jihohi da ake buƙata | duk jihohi |
| Haɗari | stack overflow | babu |
| Wurin | ana iya rage | sau da yawa kin rage zuwa O(1) layuka |
Fibonacci: daga O(2ⁿ) sauƙin zuwa O(n) lokaci, O(n) (ko O(1)) wurin.
Amfani DP lokacin da matsaloli ta overlapping. Bayyana jiha da sake tarayya da kyau — waccan ita ce karamin sashi. Idan matsaloli ba su overlapping, saukin divide-and-conquer ya isa.
DP yana jujjuya matsalolin exponential da ba'a iya jiyadeta — saiyi mafi gaba, nisan edita, akwati — zuwa mai inganci.
Wajen gane jiha da sake tarayya yana ɗaya daga cikin mafi tunani a hawaye na algorithm.
Yana kwance a zahiri tsarin daga kayan diff zuwa juyawa na jerin bioinformatics.