Annettuna on lista, jossa on positiivista kokonaislukua. Lähdet liikkelle listan alusta ja tavoitteesi on päästä listan loppuun.
Kun olet alkion kohdalla, saat hypätä 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ä on enintään , ja algoritmisi tulee toimia tehokkaasti kaikissa tapauksissa.
Toteuta tiedostoon listjump.py
funktio calculate
, joka antaa pienimmän kokonaismatkan (tai , 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 paras ratkaisu on hypätä ensin askelta oikealle, sitten askelta vasemmalle ja lopuksi askelta oikealle. Tässä askelia on yhteensä .