Vai al contenuto principale
← OlimpiApp Difficile

Informatica · Greedy

Minimo numero di salti per raggiungere la fine (variante 1)

Un array $v = [2, 3, 1, 1, 4, 2, 1, 1, 3]$ rappresenta la lunghezza massima di salto consentita da ciascuna posizione: dalla posizione i ci si può spostare a qualunque posizione tra i+1 e i+v[i] (senza uscire dall'array). Partendo dalla posizione 0, qual è il numero minimo di salti per raggiungere l'ultima posizione?