# Programazio dinamiko

Informatikan, programazio dinamikoa algoritmo baten exekuzio denbora murrizteko metodoa da. Horretarako azpi-problema gainjarriak eta azpi-egitura optimoak erabiltzen ditu.
Richard Bellman matematikariak programazio dinamikoa asmatu zuen 1953. urtean, problema konplexuak optimizatzeko, hauek sekuentzializatuz eta diskretatuz.

## Sarrera

Azpi-egitura optimo bat, azpi-problemen konponbide optimoak erabili daitezkela esan nahi du, problemaren soluzio optimoa bere osotasunean topatzeko.
Adibidez, grafo baten bi erpinen arteko biderik laburrena kalkulatu daiteke, hasierakoaren aldameneko erpin guztietatik amaiera arte bide laburrena kalkulatuz eta ondoren, emaitza hauek baliatu biderik hoberena aukeratzeko. Oro har, azpi-egitura optimoak erabiliz, problema guztiak ebatzi daitezke hiru pausu hauek jarraituz:
* Problema azpi-problema txikiagotan zatitu.
* Problema hauek era optimoan ebatzi, hiru pausuetako prozesu hau jarraituz.
* Emaitza optimo hauek erabili, problema nagusiaren soluzio optimoa eraikitzeko.
Azpi-problemak azpi-problemetan zatituz ebazten dira kasu errazera ailegatu arte, non emaitza tribiala den.
Problema batek azpi-problema gainjarriak dituela esatea, problema nagusiak ebazteko azpi-problema bera erabiltzen dela esatea da. Adibidez, Fibonacciren zenbakien segidan (F$_3$ = F$_1$ + F$_2$ y F$_4$ = F$_2$ + F$_3$) , F$_3$ eta F$_4$ kalkulatzeko, F$_2$ erabili behar da. F$_5$ kalkulatu nahi badugu, erabili F$_3$ eta F$_4$ beharko ditugu. F$_5$en inplementazio txar batek, F$_2$ bi aldiz edo gehiago kalkulatuko du. Hau beti gertatuko da azpi-problema gainjarriak ditugunean, non algoritmoaren exekuzio denbora igoko den.
Hau ekiditeko kalkulatu ditugun soluzioak zerrenda batean gorde daitezke. Beraz, problema bera berriz ebatzi nahi bada, lehen kalkulatu dugun soluzioa zerrendan bilatu dezakegu, hau berrerabiltzeko (memorizazioa).
Laburbilduz, programazio dinamikoak hauek erabiltzen ditu:
* Azpi-problema gainjarriak
* Azpi-egitura optimoak
* Memorizazioa
Gainera, bi planteamendu ezberdin azpimarra ditzakegu:
* Top-down: Problema azpi-problemetan zatitzen da, eta hauek soluzioak gogoratuz ebazten dira.
* Bottom-up: Ahal diren problema guztian aldez aurretik ebazten dira, eta ondoren, problema nagusiak ebazteko erabiltzen dira.
Programazio funtzional lengoaia batzuk, Haskell batez ere, memorizazioa erabil dezake automatikoki, prozesuak azkartzeko.

## Adibidea
### Fibonacciren zenbakiak:

Segida matematiko hau errekurtsio honekin adierazi daiteke:
    $F(n):={\begin{cases}0&{\mbox{baldin eta }}n=0;\\1&{\mbox{baldin eta }}n=1;\\F(n-1)+F(n-2)&{\mbox{baldin eta }}n>1.\\\end{cases}}$
Fibonacciren segidan n posizioan dagoen zenbakia topatzeko, honako programa errekurtsiboa sor dezakegu, kostu exponentziala eukiko duena:
Demagun fib(5) deitzen dugula, orduan zuhaitz dei bat eratuko genuke non parametro berdinak hainbat alditan errepikatuko diren:
* fib(5)
* fib(4) + fib(3)
* (fib(3) + fib(2)) + (fib(2) + fib(1))
* ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
* (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
Ikus daitekenez, hainbat alditan deitu dugu fib programa, parametro berdinekin. Parametro handiagoekin, fib balio berdin gehiago birkalkulatuko lirateke.
Arazo hau konpontzeko, problema programazio dinamikoaren bidez burutu dezakegu, memorizazioa erabiliz (kalkulatuak izan diren balioak gorde, ondoren berriz erabiltzeko). Era honetan, taula batean gordeko ditugu ateratzen joan ditugun balioak, ondoren hauek behar direnean erabiltzeko. Eratutako taula dimentsio bakarrekoa izango litzateke, 0tik n-ra.
Hau kalkulatuko luken programa, Bottom-up erabiliz:
Fibonacci funtzioak O(n)ko kostua izango du, 2^n ordez (zuhaitz bitar bat eratzen duelako memorian). Beste adibide bat, Top-Down erabilita, kalkulatutako azken bi balioekin geratzea izango litzateke, erabilgarriak direnak hurrengo zenbakiak kalkulatzeko.
Honako egitura izango luke:

## Kanpo estekak

* Datuak: Q380679