Zählen Sie Möglichkeiten, um gute Saiten zu bauen

2466. Zählen Sie Möglichkeiten, um gute Saiten zu bauen

Schwierigkeit:Mittel

Themen:Dynamische Programmierung

Angesichts der Ganzzahlen Null, Eins, Niedrig und Hoch können wir eine Zeichenfolge erstellen, indem wir mit einer leeren Zeichenfolge beginnen und dann bei jedem Schritt einen der folgenden Schritte ausführen:

• Fügen Sie das Zeichen „0“ nullmal hinzu.
• Fügen Sie das Zeichen „1“ einmal hinzu.

Dies kann beliebig oft durchgeführt werden.

Eine gute Zeichenfolge ist eine Zeichenfolge, die durch den obigen Prozess erstellt wurde und eine Länge zwischen niedrig und hoch (einschließlich) aufweist.

Gibt die Anzahl der verschiedenen guten Strings zurück, die konstruiert werden können und diese Eigenschaften erfüllen. Da die Antwort groß sein kann, geben Sie sie modulo 10⁹ 7.

zurück

Beispiel 1:

• Eingabe: niedrig = 3, hoch = 3, null = 1, eins = 1
• Ausgabe: 8
• Erklärung:
  • Eine mögliche gültige gute Zeichenfolge ist „011“.
  • Es kann wie folgt aufgebaut sein: "" -> „0“ -> "01" -> „011“.
  • Alle binären Zeichenfolgen von „000“ bis „111“ sind in diesem Beispiel gute Zeichenfolgen.

Beispiel 2:

• Eingabe: niedrig = 2, hoch = 3, null = 1, eins = 2
• Ausgabe: 5
• Erklärung:Die guten Zeichenfolgen sind „00“, „11“, „000“, „110“ und „011“.

Einschränkungen:

• 1 <= niedrig <= hoch <= 10⁵
• 1 <= null, eins <= niedrig

Hinweis:

1. Berechnen Sie die Anzahl guter Strings mit einer Länge kleiner oder gleich einer Konstante x.
2. Wenden Sie dynamische Programmierung unter Verwendung der Gruppengröße aufeinanderfolgender Nullen und Einsen an.

Lösung:

Wir müssen uns darauf konzentrieren, Zeichenfolgen unterschiedlicher Länge zu konstruieren und die Anzahl gültiger Zeichenfolgen zu zählen, die die gegebenen Bedingungen erfüllen. Lassen Sie uns den Ansatz aufschlüsseln:

Problemaufschlüsselung

1. Staatsdefinition:
   Lassen Sie dp[i] die Anzahl gültiger Zeichenfolgen der Länge i darstellen, die unter Verwendung der bereitgestellten Null- und Eins-Werte erstellt werden können.

2. Wiederholungsbeziehung:

   • Aus jeder Länge i können wir entweder Folgendes anhängen:
     • null aufeinanderfolgende Nullen, sodass die vorherige Zeichenfolge die Länge i-null hätte und wir dp[i-null] hinzufügen würden.
     • eine aufeinanderfolgende Eins, also hätte die vorherige Zeichenfolge die Länge i-eins, und wir würden dp[i-eins] hinzufügen.

Die Wiederholungsbeziehung wird:
dp[i] = dp[i – null] dpi – eins

1. Basisfall:

   • Es gibt genau eine Möglichkeit, einen leeren String zu konstruieren: dp[0] = 1.

2. Endgültige Berechnung:

   • Die Gesamtzahl der gültigen Zeichenfolgen mit einer Länge zwischen niedrig und hoch ist die Summe von dp[i] für alle i von niedrig bis hoch.

Lösungsschritte

1. Initialisieren Sie ein dp-Array der Größe hoch 1, wobei jeder Index i die Anzahl gültiger Zeichenfolgen der Länge i darstellt.
2. Durchlaufen Sie jede mögliche Länge i von 1 bis hoch und aktualisieren Sie dp[i] basierend auf der Wiederholungsbeziehung.
3. Berechnen Sie die Summe von dp[i] von niedrig nach hoch, um das Endergebnis zu erhalten.

Lassen Sie uns diese Lösung in PHP implementieren: 2466. Zählen Sie Möglichkeiten, um gute Saiten zu bauen

  
  
  Erläuterung:




Initialisierung: Wir beginnen damit, den Basisfall dp[0] = 1 festzulegen, was bedeutet, dass es eine Möglichkeit gibt, eine Zeichenfolge der Länge 0 (die leere Zeichenfolge) zu bilden.

Aktualisierung der dynamischen Programmierung: Für jede mögliche String-Länge i von 1 bis hoch prüfen wir, ob wir einen String der Länge Null oder Eins an einen kleineren String anhängen können. Wir aktualisieren dp[i] entsprechend, indem wir die Anzahl der Möglichkeiten hinzufügen, eine Zeichenfolge der Länge i-null und i-eins zu bilden, um sicherzustellen, dass das Ergebnis modulo 109 7.

Berechnung des Endergebnisses: Wir summieren alle Werte von dp[i] für i im Bereich [niedrig, hoch], um die endgültige Anzahl gültiger Zeichenfolgen zu erhalten.



  
  
  Zeitkomplexität:



Das Füllen des dp-Arrays erfordert O(hoch).

Das Summieren der gültigen Ergebnisse zwischen niedrig und hoch ergibt O(hoch – niedrig 1).



Daher beträgt die Gesamtzeitkomplexität 
** O(hoch) **, was für die Eingabegrenzen effizient genug ist.


  
  
  Raumkomplexität:



Wir verwenden ein Array dp der Größe hoch 1, daher ist die Raumkomplexität 

O(hoch).


Diese Lösung löst das Problem effizient innerhalb der Einschränkungen.



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 vonZählen Sie Möglichkeiten, um gute Saiten zu bauen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!