Разумевање динамичког програмирања: Водич за ефикасно решавање сложених проблема

ДП је скраћеница за "Динамиц Программинг". То је метода за решавање сложених проблема тако што их се разлаже на мање подпроблеме, решава сваки подпроблем само једном и чува решења подпроблема како би се избегло сувишно рачунање.ӕӕ Другим речима, ДП је техника за рекурзивно решавање проблема тако што их се разлаже на мање комаде, решавајући сваки део независно, а затим комбинујући решења делова да би се решио првобитни проблем. На тај начин можемо избећи редундантне прорачуне и ефикасније решити проблем.ӕӕДП је посебно користан за решавање проблема који имају подпроблеме који се преклапају, где се исти подпроблем може наићи више пута са различитим улазима. Чувањем решења ових подпроблема можемо избећи њихово поновно израчунавање више пута и уместо тога користити сачувана решења за брже решавање оригиналног проблема.ӕӕНеке уобичајене карактеристике ДП проблема укључују:ӕӕ* Оптимална подструктура: Проблем се може разбити на мање подпроблеми, а оптимално решење већег проблема може се конструисати из оптималних решења подпроблема.ӕ* Преклапајући подпроблеми: Исти подпроблем се може наићи више пута са различитим улазима.ӕ* Рекурзија: Проблем се може решити рекурзивно разбијањем све то на мање делове и решавање сваког дела независно.ӕӕ Примери ДП проблема укључују Фибоначијев низ, најкраћи пут у графу и најдужи заједнички подниз у два низа.