Comment trouver le nombre minimum de sauts pour atteindre la fin du tableau en O(n) fois

Question

Donné un tableau d'entiers dont chaque élément représente le nombre maximum d'étapes qui peuvent être faites avant à partir de cet élément.
Écrire une fonction pour renvoyer le nombre minimum de sauts pour atteindre le
fin du tableau (en commençant par le premier élément). Si un élément est
0, alors ne peut pas se déplacer par le biais de cet élément.

Exemple

D'entrée: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Sortie: 3 (1-> 3 -> 8 ->9)

Trouvé plusieurs façons de L'approche par Programmation dynamique à d'autres linéaire approches. Je ne suis pas en mesure de comprendre la démarche qui est dit linéaire dans le temps. ICI est le lien où une approche linéaire est proposé.

Je ne suis pas en mesure de le comprendre. Ce que j'ai pu comprendre, c'est que l'auteur suggère de faire une approche gourmande et voir si nous arrivons à la fin .. si pas alors de revenir en arrière ?

OriginalL'auteur Walt | 2015-01-09

Leave a Reply

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *