De ce contează?
Casierul îți dă restul de 6 lei și are doar bancnote de 1, 3 și 4 lei. Vrea să-ți dea cât mai puține bancnote. Nu încearcă toate combinațiile pe hârtie — se gândește: „dacă pun acum o bancnotă de 3, mai am de dat 3 lei, iar pentru 3 lei știu deja că o singură bancnotă ajunge". Restul mare se sprijină mereu pe un rest mai mic, deja rezolvat. Asta este o tranziție.
Intuiția
În programarea dinamică, o stare dp[i] e răspunsul la o subproblemă. O
tranziție este relația care spune din ce stări anterioare ajungi la i și
cu ce cost. Întrebarea-cheie e mereu aceeași: „pentru a rezolva i, ce mută
fac acum și pe ce sub-rezultat deja calculat mă sprijin?"
La restul cu monede, starea dp[s] = numărul minim de monede pentru suma s.
Ultima monedă pusă are una dintre valorile disponibile; dacă e moneda m, atunci
suma rămasă s - m e deja rezolvată optim. Deci dp[s] = 1 + min(dp[s - m]) peste
toate monedele m.