Динамичко програмирање

Појам и облици динамичког програмирања

У многим случајевима се дешава да током извршавања рекурзивне функције долази до преклапања рекурзивних позива (енгл. overlapping recursive calls) тј. да се идентични рекурзивни позиви (рекурзивни позиви са идентичним параметрима) извршавају више пута. Ако се то дешава често, програми су по правилу веома неефикасни (у многим случајевима број рекурзивних позива, па самим тим и сложеност бива експоненцијална у односу на величину улаза). До ефикаснијег решења се често може доћи техником динамичког програмирања. Оно често временску ефикасност поправља ангажовањем додатне меморије у којој се бележе резултати извршених рекурзивних позива. Динамичко програмирање долази у два облика.

• Техника мемоизације или динамичког програмирања наниже задржава рекурзивну дефиницију али у додатној структури података (најчешће низу или матрици, ређе мапи тј. речнику) бележи све резултате рекурзивних позива, да бих их у наредним позивима у којима су параметри исти само очитала из те структуре.

• Техника динамичког програмирања навише у потпуности уклања рекурзију и ту помоћну структуру података попуњава исцрпно у неком систематичном редоследу. Дакле, рекурзивна конструкција се замењује индуктивном, тј. итеративном.

Док се код мемоизације може десити да се рекурзивна функција не позива за неке вредности параметара, код динамичког програмирања навише се израчунавају вредности функције за све могуће вредности њених параметара мањих од вредности која се заправо тражи у задатку. Иако се на основу овога може помислити да је мемоизација ефикаснија техника, у пракси је чешћи случај да је током одмотавања рекурзије потребно израчунати вредност рекурзивне функције за баш велики број различитих параметара, тако да се ове предности мемоизаиције у пракси ретко среће.

Најбољи начин да разјаснимо технику динамичког програмирања је да је илуструјемо на низу погодно одабраних примера. Кренућемо од Фибоначијевог низа, који је опште познати проблем и кроз чије се решавање могу илустровати већина основних концепата динамичког програмирања.