Tabulare vs memoizare: costul minim pe scări
Aceeași scară, dar acum fiecare treaptă are un cost (de exemplu, energia consumată). Nu mai numeri moduri, ci cauți drumul cel mai ieftin. Vei scrie problema în ambele stiluri de DP și vei reduce memoria de la O(n) la O(1).
Problema
Primești lista cost, unde cost[i] este prețul plătit când pui piciorul pe treapta i. Poți porni de pe treapta 0 sau de pe treapta 1, iar după fiecare treaptă urci 1 sau 2 trepte. Ținta este vârful, adică poziția n = len(cost), de după ultima treaptă (vârful nu costă nimic).
Scrie funcția cost_minim(cost) care returnează costul minim până la vârful scării, în varianta tabelară (bottom-up), fără recursivitate. Pentru punctaj maxim, folosește doar două variabile (O(1) spațiu). Testele sunt deja scrise.
- Pornește cu două variabile egale cu 0 (costul de a ajunge pe treptele 0 și 1).
- Pentru fiecare poziție de la 2 la len(cost), calculează minimul dintre cele două variante.
- Glisează variabilele și returnează ultima valoare. Trebuie să apară: 15, 6, 0.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan