Steinspiel II

1140. Steinspiel II

Schwierigkeit:Mittel

Themen: Array, Mathematik, dynamische Programmierung, Präfixsumme, Spieltheorie

Alice und Bob setzen ihre Spiele mit Steinhaufen fort. Es gibt eine Reihe von Stapeln, die in einer Reihe angeordnet sind, und jeder Stapel hat eine positive ganze Zahl von Steinstapeln[i]. Das Ziel des Spiels ist es, mit den meisten Steinen zu enden.

Alice und Bob wechseln sich ab, wobei Alice als Erste beginnt. Anfangs,M = 1.

Wenn jeder Spieler an der Reihe ist, kann dieser Spieler alle Steine in den ersten X verbleibenden Stapeln nehmen, wobei 1 <= X <= 2M. Dann setzen wir M = max(M, X).

Das Spiel geht weiter, bis alle Steine ​​genommen wurden.

Angenommen, Alice und Bob spielen optimal, gib die maximale Anzahl an Steinen zurück, die Alice bekommen kann.

Beispiel 1:

• Eingabe: Stapel = [2,7,9,4,4]
• Ausgabe: 10
• Erklärung: Wenn Alice am Anfang einen Stapel nimmt, nimmt Bob zwei Stapel, dann nimmt Alice wieder 2 Stapel. Alice kann insgesamt 2 + 4 + 4 = 10 Stapel bekommen. Wenn Alice zu Beginn zwei Stapel nimmt, kann Bob alle drei verbleibenden Stapel nehmen. In diesem Fall erhält Alice insgesamt 2 + 7 = 9 Stapel. Wir geben also 10 zurück, da es größer ist.

Beispiel 2:

• Eingabe: Stapel = [1,2,3,4,5,100]
• Ausgabe: 104

Einschränkungen:

• 1 <= Pfähle.Länge <= 100
• 1 <= Stapel[i] <= 10⁴

Hinweis:

1. Verwenden Sie dynamische Programmierung: Die Zustände sind (i, m) für die Antwort von Stapeln[i:] und das gegebene m.

Lösung:

Wir müssen dynamische Programmierung verwenden, um die maximale Anzahl an Steinen zu ermitteln, die Alice erhalten kann, wenn beide Spieler optimal spielen. Hier ist ein schrittweiser Ansatz zur Entwicklung der Lösung:

1. Zustand und Übergang definieren:

   • Definieren Sie ein 2D-DP-Array, wobei dp[i][m] die maximale Menge an Steinen darstellt, die Alice ab Stapel i mit einem maximalen Auswahllimit m sammeln kann.
   • Verwenden Sie ein Präfix-Summen-Array, um die Summe der Steine ​​in Unterarrays effizient zu berechnen.

2. Basisfall:

   • Wenn keine Steine ​​mehr zum Pflücken übrig sind, ist die Punktzahl 0.

3. Rekursiver Fall:

   • Berechnen Sie für jeden Stapel i und die maximal zulässige Auswahl m die maximale Menge an Steinen, die Alice sammeln kann, indem Sie alle möglichen Züge berücksichtigen (wobei 1 bis 2 m Stapel genommen werden).

4. Übergangsfunktion:

   • Berechnen Sie für jede mögliche Anzahl von Stapeln, die Alice auswählen kann, die Gesamtzahl der Steine, die Alice erhalten kann, und verwenden Sie die Ergebnisse zukünftiger Zustände, um den optimalen Zug zu entscheiden.

Lassen Sie uns diese Lösung in PHP implementieren: 1140. Steinspiel II

stoneGameII($piles1) . "\n"; // Output: 10
echo $solution->stoneGameII($piles2) . "\n"; // Output: 104
?>






  
  
  Erläuterung:




Präfix-Summenberechnung: Dies hilft bei der schnellen Berechnung der Summe der Steine ​​von jedem Stapel i bis j.

DP-Array-Initialisierung: dp[i][m] enthält die maximalen Steine, die Alice ausgehend von Stapel i erhalten kann, mit einem maximalen Auswahllimit von m.

Übergang zur dynamischen Programmierung: Berechnen Sie für jeden Stapel und jedes m die maximale Menge an Steinen, die Alice sammeln kann, indem Sie die möglichen Stapelanzahlen durchlaufen, die sie aufnehmen kann, und das DP-Array entsprechend aktualisieren.


Dieser Ansatz stellt sicher, dass die Lösung effizient berechnet wird, und nutzt die Vorteile der dynamischen Programmierung, um redundante Berechnungen zu vermeiden.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonSteinspiel II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!