Minimale Anzahl von Schritten, die erforderlich sind, um den letzten Index zu erreichen

Question

Bei einem Array nicht negativer Ganzzahlen sind Sie zunächst am ersten Index des Arrays positioniert.

Jedes Element im Array repräsentiert Ihre maximale Sprunglänge an dieser Position.

Ihr Ziel ist es, den letzten Index in der minimalen Anzahl von Sprüngen zu erreichen.

Zum Beispiel: Wechsel (1 Stufe aus dem Index 0 auf 1 gegebene Gruppe A = [2,3,1,1,4]

Die minimale Anzahl von Sprüngen den letzten Index zu erreichen, 2. ist, dann 3 Schritte zum letzten Index.)

Ich habe ein dp [] Array von links nach rechts so gebaut, dass dp [i] die minimale Anzahl von Sprüngen angibt, die benötigt werden, um arr [i] von arr [0] zu erreichen. Schließlich geben wir dp [n-1] zurück.

Worst Case-Zeit Komplexität meines Codes ist O (n^2).

Kann dies in einer besseren Zeit Komplexität getan werden.

** Diese Frage wird vom Leetcode kopiert.

Answer 1

Ich denke, Sie können die Berechnung der Dynamik mit diesen Techniken beschleunigen:
Sie verbringen O (N) für Rechenstrom d [i]. Aber Sie können einen Satz mit d [j], wo j = 0..i - 1. Und jetzt alles, was Sie brauchen, binäre Suche zu finden:

so d [j], das ist das Minimum unter allen (0..i-1) und von j Position i-pos ist erreichbar.

Es wird O (n * logn) Lösung

Answer 2

sein, dass eine einfache Übung in dynamischer Programmierung ist. Wie Sie es bereits markiert haben, frage ich mich, warum Sie nicht versuchen, es anzuwenden.

Lassen Sie V[k] die minimale Anzahl von Schritten sein, um von Position k bis zum Ende der Liste a = (a[0], a[1], ...., a[n-1]) zu gelangen.

Dann offensichtlich V[n-1]=0. Nun Schleife rückwärts:

for(int k=n-2;k>=0;--k) 
{ 
    int minStep = n + 1; 
    for(int j=k+1;j<=std::min(n-1,k+a[k]);++j) 
    { 
     minStep = std::min(minStep, V[j]) 
    } 
    V[k]= minStep + 1; 
} 

Demo in C++

Nach der Schleife, die O(a[0]+a[1]+...+a[n-1]) Zeit in Anspruch nimmt, V[0] enthält die minimale Anzahl von Schritten, das Ende der Liste zu erreichen.

Um den Weg durch die Liste zu finden, können Sie dann die Aktion gierig wählen. Das heißt, von Position k gehen Sie immer zu einer zulässigen Position l wo V[l] minimal ist.

(Beachten Sie, dass ich positive Einträge der Liste hier nicht nicht-negative angenommen habe. Mögliche Nullen können leicht aus dem Problem entfernt werden, da es nie optimal ist, dorthin zu gehen.)