Se citesc n trepte ale unei scari, fiecare cu un cost asociat. Puteti incepe urcarea de pe treapta 0 sau de pe treapta 1 (fara niciun cost initial) si, din orice treapta, puteti urca fie o treapta, fie doua trepte deodata, platind de fiecare data costul treptei pe care ajungeti. Determinati, folosind Programarea Dinamica, costul minim pentru a ajunge dincolo de ultima treapta (dupa treapta n-1).
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n costuri.
- Date de iesire
- Se afiseaza un singur numar: costul minim total.
- Restrictii
- 1 <= n <= 100000, 0 <= cost <= 1000
Exemple
Exemplul 1
Intrare
2 10 15
Iesire
10
Exemplul 2
Intrare
3 10 15 20
Iesire
15