650. 2-Tasten-Tastatur

Schwierigkeit: Mittel

Themen: Mathematik, dynamische Programmierung

Es gibt nur ein Zeichen „A“ auf dem Bildschirm eines Notizblocks. 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.

Gib bei einer gegebenen Ganzzahl n 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: 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

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 anzuzeigen. 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 „Alles 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 zu haben.
   • 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 Operationen berücksichtigen, die zum Erreichen von d erforderlich sind, 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