Maximale Anzahl von Zügen in einem Raster

Linda Hamilton
Freigeben: 2024-10-30 13:27:03
Original
276 Leute haben es durchsucht

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:

Maximum Number of Moves in a Grid

  • 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:

Maximum Number of Moves in a Grid

  • 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 <= 105
  • 1 <= Gitter[i][j] <= 106

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:

  1. dp-Initialisierung: Wir erstellen ein 2D-Array dp, um die maximalen Bewegungen aus jeder Zelle zu speichern.
  2. 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.
  3. 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!

Quelle:dev.to
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Neueste Artikel des Autors
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!