Memoization vs tabulation
Në shqip: Memoizimi kundrejt tabelimit
ShpjegimiSQ
Programimi dinamik bëhet në dy mënyra: „nga lart poshtë“ (rekursion + memoizim — mban mend rezultatet) ose „nga poshtë lart“ (tabelim — mbush një tabelë nga rastet më të vogla). Tabelimi shmang stack overflow.
EnglishEN
Dynamic programming comes in two styles: “top-down” (recursion + memoisation — remember results) or “bottom-up” (tabulation — fill a table from the smallest cases). Tabulation avoids stack overflow.
Si ta mendosh
Si të ngjitesh shkallëve duke mbajtur mend çdo shkallë, ose duke i numëruar nga poshtë.
Lexoje në anglisht
Like climbing stairs remembering each step, versus counting them from the bottom up.
Shembull kodipython
def fib(n):
dp = [0, 1] + [0] * (n - 1)
for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]