. Seltsamer Drucker

664. Seltsamer Drucker

Schwierigkeit:Schwer

Themen:String, dynamische Programmierung

Es gibt einen seltsamen Drucker mit den folgenden zwei besonderen Eigenschaften:

• Der Drucker kann jedes Mal nur eine Folge von dem gleichen Zeichen drucken.
• Bei jedem Zug kann der Drucker neue Zeichen drucken, die an einer beliebigen Stelle beginnen und enden, und überdeckt dabei die ursprünglich vorhandenen Zeichen.

Geben Sie bei einer gegebenen Zeichenfolge s die Mindestanzahl an Umdrehungen zurück, die der Drucker zum Drucken benötigte.

Beispiel 1:

• Eingabe: s = "aaabbb"
• Ausgabe: 2
• Erklärung: Geben Sie zuerst „aaa“ und dann „bbb“ ein.

Beispiel 2:

• Eingabe: s = "aba"
• Ausgabe: 2
• Erklärung: Geben Sie zuerst „aaa“ und dann „b“ ab der zweiten Stelle der Zeichenfolge aus, wodurch das vorhandene Zeichen „a“ überdeckt wird.

Einschränkungen:

• 1 <= s.length <= 100
• s besteht aus englischen Kleinbuchstaben.

Lösung:

Wir können dynamische Programmierung verwenden. Die Idee besteht darin, die Anzahl der zum Drucken der Zeichenfolge erforderlichen Windungen zu minimieren, indem man sie in Teilprobleme aufteilt.

Das Problem kann durch dynamische Programmierung gelöst werden. Die Idee besteht darin, das Problem in kleinere Teilprobleme zu unterteilen, wobei Sie die Mindestumdrehungen bestimmen, die zum Drucken jedes Teilstrings von s erforderlich sind. Wir können die folgende Beobachtung nutzen:

• Wenn zwei benachbarte Zeichen gleich sind, können Sie einen vorherigen Vorgang verlängern, anstatt ihn als neuen Vorgang zu zählen.

Dynamische Programmierlösung

Sei dp[i][j] die minimale Anzahl an Umdrehungen, die zum Drucken der Teilzeichenfolge s[i:j+1] erforderlich sind.

1. Wenn s[i] == s[j], dann ist dp[i][j] = dp[i][j-1], da das letzte Zeichen s[j] mit der vorherigen Operation gedruckt werden kann.
2. Andernfalls gilt dp[i][j] = min(dp[i][k] + dp[k+1][j]) für alle i <= k < j.

Lassen Sie uns diese Lösung in PHP implementieren: 664. Seltsamer Drucker

  
  
  Erläuterung:



DP-Array: Das 2D-Array dp[i][j] stellt die minimale Anzahl von Umdrehungen dar, die erforderlich sind, um den Teilstring von Index i bis j zu drucken.
Initialisierung: Wir initialisieren dp[i][i] = 1, da ein einzelnes Zeichen in einer Runde gedruckt werden kann.

Füllen der DP-Tabelle:


Wenn die Zeichen bei i und j gleich sind ($s[$i] == $s[$j]), dauert das Drucken von i nach j genauso viele Runden wie das Drucken von i nach j-1 da $s[$j] ​​im selben Zug wie $s[$i] gedruckt werden kann.
Wenn sie unterschiedlich sind, versuchen wir die minimale Anzahl von Windungen zu finden, indem wir die Saite an verschiedenen Punkten (k) teilen.


Ergebnis: Die Mindestanzahl an Umdrehungen, die zum Drucken der gesamten Zeichenfolge erforderlich sind, wird in dp[0][$n - 1] gespeichert.


Diese Lösung berechnet effizient die Mindestanzahl der zum Drucken der Zeichenfolge erforderlichen Windungen, indem alle möglichen Möglichkeiten zum Teilen und Drucken der Zeichenfolge berücksichtigt werden.

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 von. Seltsamer Drucker. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!