Dinaminis programavimas: Skirtumas tarp puslapio versijų

'''Dinaminis programavimas''' – [[Programavimas|programavimo]] metodas, paremtas uždavinio skaidymu į mažesnes susijusias problemas, bei tų problemų sprendimų įsiminimu. Taigi laiko sanaudos pakeičiamos atminties sanaudomis. Jis naudojamas, kuomet „[[Skaldyk ir valdyk]]“ nėra pakankamai efektyvus. Gali būti pritaikomas įvairaus tipo uždaviniams, tačiau šio metodo taikymo galimybę pastebėti ne visuomet lengva.

 

Apibrėžimas: <math>F_n=F_{n-1}+F_{n-2}</math>, <math>F_1=1</math>, <math>F_2=1</math>. Reikia apskaičiuoti <math>n</math>-tąjį sekos narį. Rekursyvus sprendimas būtų toks:

 

end;

 

Šio tipo uždaviniai gana dažni. Bendrai jie formuluojami taip: turime <math>N</math> daiktų, bei žinome jų dydžius <math>D_i</math> bei vertes <math>V_i</math>. Kuprinės dydis yra <math>K</math>, taigi galima paimti tik tiek daiktų, kad jų dydis neviršytų <math>K</math>. Reikia surasti tokį daiktų rinkinį, kurio vertė būtų didžiausia.