. eys Tastatur

650. 2-Tasten-Tastatur

Schwierigkeit:Mittel

Themen:Mathematik, dynamische Programmierung

Auf dem Bildschirm eines Notizblocks gibt es nur ein Zeichen „A“. Sie können für jeden Schritt einen von zwei Vorgängen auf diesem Notizblock ausführen:

• Alle kopieren: Sie können alle auf dem Bildschirm vorhandenen Zeichen kopieren (ein teilweises Kopieren ist nicht zulässig).
• Einfügen: Sie können die zuletzt kopierten Zeichen einfügen.

Gegeben eine ganze Zahl n, gibdie minimale Anzahl von Operationen zurück, um das Zeichen „A“ genau n-mal auf dem Bildschirm zu erhalten.

Beispiel 1:

• Eingabe:n = 3
• Ausgabe:3
• Erklärung:Zunächst haben wir ein Zeichen „A“.
  • In Schritt 1 verwenden wir den Vorgang „Alle kopieren“.
  • In Schritt 2 verwenden wir den Einfügen-Vorgang, um „AA“ zu erhalten.
  • In Schritt 3 verwenden wir den Einfügen-Vorgang, um „AAA“ zu erhalten.

Beispiel 2:

• Eingabe:n = 1
• Ausgabe:0

Beispiel 3:

• Eingabe:n = 10
• Ausgabe:7

Beispiel 2:

• Eingabe:n = 24
• Ausgabe:9

Einschränkungen:

• 1 <= n <= 1000

Hinweis:

1. Wie viele Zeichen dürfen sich im letzten Schritt in der Zwischenablage befinden, wenn n = 3? n = 7? n = 10? n = 24?

Lösung:

Wir müssen die Mindestanzahl an Operationen finden, um genau n Zeichen „A“ auf dem Bildschirm zu erhalten. Um dies zu erreichen, verwenden wir einen dynamischen Programmieransatz.

1. Das Problem verstehen:

   • Wir beginnen mit einem „A“ auf dem Bildschirm.
   • Wir können entweder „Alle kopieren“ (wodurch der aktuelle Bildschirminhalt kopiert wird) oder „Einfügen“ (wodurch der zuletzt kopierte Inhalt eingefügt wird) wählen.
   • Wir müssen die Mindestoperationen ermitteln, die erforderlich sind, um genau n Zeichen „A“ auf dem Bildschirm zu haben.

2. Dynamischer Programmieransatz:

   • Verwenden Sie ein dynamisches Programmierarray (DP) dp, wobei dp[i] die minimale Anzahl von Operationen darstellt, die erforderlich sind, um genau i Zeichen auf dem Bildschirm zu erhalten.
   • Initialisieren Sie dp[1] = 0, da 0 Vorgänge erforderlich sind, um ein „A“ auf dem Bildschirm anzuzeigen.
   • Berechnen Sie für jede Anzahl von Zeichen i von 2 bis n die Mindestoperationen, indem Sie jeden Teiler von i überprüfen. Wenn i durch d teilbar ist, dann gilt:
     • Die Anzahl der Operationen, die erforderlich sind, um i zu erreichen, ist die Summe der Operationen, um d zu erreichen, plus der Operationen, die erforderlich sind, um d zu multiplizieren, um i zu erhalten.

3. Schritte zur Lösung:

   • Initialisieren Sie ein DP-Array mit INF (oder einer großen Zahl) für alle Werte außer dp[1].
   • Iterieren Sie für jedes i von 2 bis n mögliche Teiler von i und aktualisieren Sie dp[i] basierend auf den Operationen, die erforderlich sind, um i durch Kopieren und Einfügen zu erreichen.

Lassen Sie uns diese Lösung in PHP implementieren:650. 2-Tasten-Tastatur

        
Erläuterung:
        

         
Initialisierung:dp wird mit einer großen Zahl (PHP_INT_MAX) initialisiert, um einen zunächst nicht erreichbaren Zustand darzustellen.
         
Teilerprüfung:Überprüfen Sie für jede Zahl i alle Teiler d. Aktualisieren Sie dp[i], indem Sie die zum Erreichen von d erforderlichen Operationen berücksichtigen und dann multiplizieren, um i zu erhalten.
         
Ausgabe:Das Ergebnis ist der Wert von dp[n], der die minimal erforderlichen Operationen angibt, um genau n Zeichen auf den Bildschirm zu bringen.
        
Dieser Ansatz stellt sicher, dass wir die Mindestoperationen für die gegebenen Einschränkungen effizient berechnen.
Kontaktlinks
Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, demRepositoryeinen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Eure 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. eys Tastatur. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!