Programarea dinamică: urcarea scărilor
Ultimul modul al cursului începe cu cea mai temută temă de la interviuri: programarea dinamică (DP). Vestea bună: ideea de bază e simplă. Dacă o problemă se poate împărți în subprobleme care se repetă, calculezi fiecare subproblemă o singură dată și ții minte rezultatul.
Problema: în câte moduri urci scările?
Un curier urcă scările unui bloc. La fiecare pas poate urca 1 treaptă sau 2 trepte. În câte moduri diferite poate ajunge pe treapta n?
Scrie funcția moduri_scari(n) care returnează în câte moduri se pot urca n trepte (câte 1 sau 2 o dată), folosind un tabel dp (varianta bottom-up, fără recursivitate). Testele sunt deja scrise.
- Tratează separat cazurile n <= 2 (răspunsul este chiar n).
- Creează dp = [0] * (n + 1) și completează-l de la 3 la n.
- Returnează dp[n]. Trebuie să apară: 1, 2, 8, 89, 1836311903.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan