Annettuna on lista, jossa on alkiota. Jokainen alkio on kokonaisluku väliltä .
Lähdet liikkelle listan alusta, ja aina kun olet alkion kohdalla, saat hypätä askelta vasemmalle tai oikealle. Et saa kuitenkaan tehdä hyppyä, joka veisi listan ulkopuolelle. Tavoitteesi on päästä listan loppuun niin, että hyppyjen kokonaismatka on mahdollisimman pieni.
Esimerkiksi listassa paras ratkaisu on hypätä ensin askelta oikealle, sitten askelta vasemmalle ja lopuksi askelta oikealle. Tässä askelia on yhteensä .
Voit olettaa, että on enintään . Jos mitään ratkaisua ei ole olemassa, palauta .
Toteuta tiedostoon listjump.py
funktio calculate
, joka antaa pienimmän kokonaismatkan.
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