. 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, geben Sie die 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: Am Anfang haben wir ein Zeichen „A“.
  • In Schritt 1 verwenden wir den Vorgang „Alle kopieren“.
  • In Schritt 2 verwenden wir den Einfügevorgang, um „AA“ zu erhalten.
  • In Schritt 3 verwenden wir den Einfügevorgang, 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 im letzten Schritt in der Zwischenablage vorhanden sein, 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 bestimmen, 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 Operationen 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 dem Bildschirm zu erhalten.


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