Maximale Anzahl von Zügen in einem Raster

2684. Maximale Anzahl von Zügen in einem Raster

Schwierigkeit:Mittel

Themen:Array, Dynamische Programmierung, Matrix

Sie erhalten ein 0-indiziertes m x n-Matrixgitter, das aus positiven ganzen Zahlen besteht.

Sie können bei jeder Zelle in der ersten Spalte der Matrix beginnen und das Raster auf folgende Weise durchlaufen:

• Von einer Zelle (Zeile, Spalte) aus können Sie zu einer der folgenden Zellen wechseln: (Zeile - 1, Spalte 1), (Zeile, Spalte 1) und (Zeile 1, Spalte 1), sodass der Wert der Die Zelle, in die Sie wechseln, sollte unbedingt größer sein als der Wert der aktuellen Zelle.

Geben Sie die maximale Anzahl an Zügen zurück, die Sie ausführen können.

Beispiel 1:

• Eingabe: Gitter = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15] ]
• Ausgabe: 3
• Erklärung: Wir können bei der Zelle (0, 0) beginnen und die folgenden Schritte ausführen:
  • (0, 0) -> (0, 1).
  • (0, 1) -> (1, 2).
  • (1, 2) -> (2, 3). Es kann gezeigt werden, dass es sich um die maximale Anzahl an Zügen handelt, die gemacht werden können.

Beispiel 2:

• Eingabe: Gitter = [[3,2,4],[2,1,9],[1,1,7]]
• Ausgabe: 0
• Erklärung:Ausgehend von einer beliebigen Zelle in der ersten Spalte können wir keine Züge ausführen.

Einschränkungen:

• m == Gitterlänge
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 10⁵
• 1 <= Gitter[i][j] <= 10⁶

Hinweis:

1. Erwägen Sie die Verwendung dynamischer Programmierung, um die maximale Anzahl von Zügen zu ermitteln, die von jeder Zelle aus ausgeführt werden können.
2. Die endgültige Antwort ist der Maximalwert in den Zellen der ersten Spalte.

Lösung:

Wir können Dynamische Programmierung (DP) verwenden, um die maximale Anzahl von Zügen aus jeder Zelle zu verfolgen, beginnend mit jeder Zelle in der ersten Spalte. Hier ist die Schritt-für-Schritt-Anleitung:

Ansatz:

1. DP-Array definieren: Lassen Sie dp[row][col] die maximale Anzahl möglicher Züge darstellen, beginnend mit Grid[row][col]. Initialisieren Sie dies mit 0 für alle Zellen.

2. Durchquere das Gitter:

   • Beginnen Sie mit der letzten Spalte und gehen Sie rückwärts zur ersten Spalte. Berechnen Sie für jede Zelle in der Spalte Spalte die möglichen Bewegungen für Spalte 1.
   • Aktualisieren Sie dp[Zeile][Spalte] basierend auf möglichen Verschiebungen (Zeile - 1, Spalte 1), (Zeile, Spalte 1) und (Zeile 1, Spalte 1), nur wenn der Wert der Zielzelle < ist 🎜>unbedingt größer als die aktuelle Zelle.

3. Berechnen Sie die maximalen Bewegungen:

   Nach dem Ausfüllen der dp-Tabelle ist das Ergebnis der Maximalwert in der ersten Spalte von dp, da er die maximalen Bewegungen ab einer beliebigen Zelle in der ersten Spalte darstellt.

4. Edge Cases:

   Behandeln Sie Fälle, in denen keine Bewegungen möglich sind (z. B. wenn alle Pfade durch niedrigere oder gleiche Werte in benachbarten Zellen blockiert sind).

Lassen Sie uns diese Lösung in PHP implementieren:

2684. Maximale Anzahl von Zügen in einem Raster

  
  
  Erläuterung:




dp-Initialisierung: Wir erstellen ein 2D-Array dp, um die maximalen Bewegungen aus jeder Zelle zu speichern.

Schleife durch Spalten: Wir iterieren von der vorletzten Spalte zur ersten und aktualisieren dp[row][col] basierend auf möglichen Verschiebungen in benachbarte Zellen in der nächsten Spalte.

Berechnung der maximalen Bewegungen: Schließlich ergibt der Maximalwert in der ersten Spalte von dp das Ergebnis.



  
  
  Komplexitätsanalyse:




Zeitkomplexität: O(m x n)da wir jede Zelle einmal verarbeiten.

Raumkomplexität: O(m x n) für das dp-Array.


Diese Lösung ist angesichts der Einschränkungen effizient und funktioniert innerhalb der vorgegebenen Grenzen.



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 vonMaximale Anzahl von Zügen in einem Raster. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!