Tabulare vs memoizare: costul minim pe scări
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.
[0, 0] poți porni direct de pe treapta 1 și sări pe vârf: costul este 0.def cost_minim(cost):
doi_inainte, unu_inainte = 0, 0
for i in range(2, len(cost) + 1):
curent = min(unu_inainte + cost[i - 1], doi_inainte + cost[i - 2])
doi_inainte, unu_inainte = unu_inainte, curent
return unu_inainte
print(cost_minim([10, 15, 20]))
print(cost_minim([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
print(cost_minim([0, 0]))


