Probleme ce folosesc optimul de la pasul anterior sau un număr constant de pași anteriori

Aceste probleme au de regulă complexitate liniară (după numărul stărilor la care avem de calculat optimul). Motivul este că valoarea stării curente depinde doar de una sau de un număr constant de stări anterioare. Astfel ea se calculează fără repetiții suplimentare.