Dynamicke programovanie je metoda riesenia problemov, ktore vykazuju vlastnost prekryvajucich sa podproblemov, alebo optimalnej podstruktury. Prekryvajuce sa podproblemy znamenaju, ze rovnake podproblemy su pouzite pre stale vacsie problemy (down-top pristup - pozri algoritmus). Ak ma problem optimalnu podstrukturu, tak optimalne riesenie podproblemov vedie k rieseniu celeho problemu.
Dynamicke programovanie riesi napriklad najdenie optimalneho BVS, Fibonnaciho cisla, priechod ohodnotenym polom.
Najdenie optimalneho BVS
Je dana mnozina prvkov, v ktorej chceme vyhladavat a pravdepodobnost, s ktorou budeme vyhladavat dany provok. Ulohou je zostavit BVS tak, aby priemerna doba vyhladania jedneho prvku bola co najmensia. Najcastejsie hladane prvky budu co najlbizsie ku korenu stromu.
