Autori: Andreja Ilić i Aleksandar Ilić
Jedan od čestih algoritamskih problema jeste problem optimizacije: zadati problem može imati više rešenja, svako rešenje ima svoju vrednost, a traži se ono koje ima ekstremnu vrednost. U jednoj širokoj klasi problema optimizacije, rešenje možemo naći korišćenjem dinamičkog programiranja (eng. dynamic programming).
Teorijski gledano probleme optimizacije, kao i probleme pretrage, možemo rešiti simulacijom svih stanja, odnosno obilaskom celokupnog prostora pretrage (eng. backtracking). Ovo je naravno korektan pristup, medjutim on nije upotrebljiv za probleme sa velikim brojem stanja. Takodje, možemo koristiti grabljivi pristup (eng. greedy algorithm), koji se zasniva na biranju lokalnog najboljeg poteza u svakoj tački grananja. Ova vrsta heuristike može znatno smanjiti složenost i prostor pretrage, ali se ne može tvrditi njena tačnost.
Ideja dinamičkog programiranja je da se iskoristi princip domina: sve nanizane domine će popadati ako se poruši prva domina u nizu. Dakle, da bi se rešio neki problem, treba rešiti neki njegov manji slučaj (podproblem), a zatim pokazati kako se rešenje zadatog problema može konstruisati polazeći od (rešenih) podproblema. Ovakav pristup je baziran na matematičkoj indukciji.