Annettuna on lista, jossa on n positiivista kokonaislukua. Lähdet liikkelle listan alusta ja tavoitteesi on päästä listan loppuun.
Kun olet alkion x kohdalla, saat hypätä x askelta vasemmalle tai oikealle. Et saa kuitenkaan tehdä hyppyä, joka veisi listan ulkopuolelle. Sinun tulee päästä listan loppuun niin, että askelten kokonaismäärä on mahdollisimman pieni.
Esimerkiksi listassa [3,5,2,2,2,3,5] paras ratkaisu on hypätä ensin 3 askelta oikealle, sitten 2 askelta vasemmalle ja lopuksi 5 askelta oikealle. Tässä askelia on yhteensä 3+2+5=10.
Toteuta tiedostoon listjump.py funktio find_steps, joka antaa pienimmän askelten kokonaismäärän. Funktion tulee palauttaa -1, jos ei ole mahdollista päästä listan loppuun.
Funktion tulee toimia tehokkaasti myös silloin, kun listan pituus on suuri. Tehtäväpohjan viimeinen funktiokutsu testaa tällaista tapausta.
def find_steps(numbers):
# TODO
if __name__ == "__main__":
print(find_steps([1, 1, 1, 1])) # 3
print(find_steps([3, 2, 1])) # -1
print(find_steps([3, 5, 2, 2, 2, 3, 5])) # 10
print(find_steps([7, 5, 3, 1, 4, 2, 4, 6, 1])) # 32
numbers = []
for i in range(10**5):
numbers.append(1337 * i % 100 + 1)
print(find_steps(numbers)) # 100055