De ce contează?
Urci o scară cu 6 trepte și poți face, la fiecare pas, ori un salt de 1 treaptă, ori unul de 2. În câte moduri diferite ajungi sus? Ai putea încerca să numeri pe hârtie toate drumurile — dar te încurci repede. Trucul e altul: ca să ajungi pe treapta 6, ultimul tău salt a venit ori de pe treapta 5, ori de pe treapta 4. Deci numărul de drumuri până la 6 e suma drumurilor până la 5 și până la 4. Dacă știi răspunsul pentru treptele mici, îl construiești pe cel mare fără să mai numeri nimic de la zero.
Intuiția
Programarea dinamică rezolvă o problemă spărgând-o în subprobleme care se
suprapun: aceleași bucăți mici apar iar și iar. Ideea-cheie e să calculezi
fiecare subproblemă o singură dată și să-i reții răspunsul, ca să nu-l mai
refaci niciodată. La scară, „câte moduri ajung pe treapta i” depinde doar de
treptele de dedesubt — deci urci tabelul de jos în sus, fiecare treaptă folosind
răspunsurile deja gata ale celor de sub ea.