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ä hyppyjen kokonaismatka on mahdollisimman pieni.
Voit olettaa, että n on enintään 10^5, ja algoritmisi tulee toimia tehokkaasti kaikissa tapauksissa.
Toteuta tiedostoon listjump.py funktio calculate, joka antaa pienimmän kokonaismatkan (tai -1, jos ei ole mahdollista päästä listan loppuun).
def calculate(t):
# TODO
if __name__ == "__main__":
print(calculate([1, 1, 1, 1])) # 3
print(calculate([3, 2, 1])) # -1
print(calculate([3, 5, 2, 2, 2, 3, 5])) # 10
print(calculate([7, 5, 3, 1, 4, 2, 4, 6, 1])) # 32
Selitys: 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.