. Mindestpreis für Tickets

983. Mindestpreis für Tickets

Schwierigkeit:Mittel

Themen:Array, dynamische Programmierung

Sie haben ein Jahr im Voraus einige Zugreisen geplant. Die Tage des Jahres, in denen Sie reisen, werden als ganzzahlige Array-Tage angegeben. Jeder Tag ist eine Ganzzahl von 1 bis 365.

Bahntickets werden auf drei verschiedene Arten verkauft:

• Ein 1-Tages- Pass wird für [0] Dollar verkauft,
• Ein 7-Tagespass wird zum Preis von[1] Dollar verkauft und
• Ein 30-Tagespass wird zum Preis von[2] Dollar verkauft.

Die Pässe ermöglichen so viele aufeinanderfolgende Reisetage.

• Wenn wir beispielsweise am zweiten Tag einen 7-Tages- Pass erhalten, können wir 7 Tage lang reisen: 2, 3, 4, 5, 6, 7 und 8.

Geben Sie den Mindestbetrag an Dollar zurück, den Sie täglich für die Reise in der angegebenen Tagesliste benötigen.

Beispiel 1:

• Eingabe: Tage = [1,4,6,7,8,20], Kosten = [2,7,15]
• Ausgabe: 11
• Erklärung: Hier ist beispielsweise eine Möglichkeit, Pässe zu kaufen, mit denen Sie Ihren Reiseplan umsetzen können:
  • Am ersten Tag haben Sie eine Tageskarte zum Preis von [0] = 2 $ gekauft, die den ersten Tag abdeckte.
  • Am 3. Tag haben Sie einen 7-Tage-Pass für die Kosten[1] = 7 $ gekauft, der die Tage 3, 4, ..., 9 abdeckt.
  • Am 20. Tag haben Sie zum Preis von [0] = 2 $ eine Tageskarte gekauft, die den 20. Tag abdeckte.
  • Insgesamt haben Sie 11 $ ausgegeben und alle Tage Ihrer Reise abgedeckt.

Beispiel 2:

• Eingabe: Tage = [1,2,3,4,5,6,7,8,9,10,30,31], Kosten = [2,7,15]
• Ausgabe: 17
• Erklärung: Hier ist beispielsweise eine Möglichkeit, Pässe zu kaufen, mit denen Sie Ihren Reiseplan umsetzen können:
  • Am ersten Tag haben Sie einen 30-Tage-Pass für die Kosten[2] = 15 $ gekauft, der die Tage 1, 2, ..., 30 abdeckt.
  • Am 31. Tag haben Sie eine Tageskarte zum Preis von [0] = 2 $ gekauft, die den 31. Tag abdeckt.
  • Insgesamt haben Sie 17 $ ausgegeben und alle Tage Ihrer Reise abgedeckt.

Einschränkungen:

• 1
• 1
• Tage ist in streng aufsteigender Reihenfolge.
• costs.length == 3
• 1

Lösung:

Das Problem besteht darin, die Mindestkosten für Reisen an bestimmten Tagen im Jahr zu ermitteln. Das Problem bietet drei Arten von Reisepässen: 1-Tages-, 7-Tages- und 30-Tages-Pässe, jeweils mit spezifischen Kosten. Ziel ist es, mit diesen Pässen die günstigste Möglichkeit zu finden, alle Reisetage abzudecken. Die Aufgabe erfordert die Verwendung dynamischer Programmierung, um die minimalen Kosten effizient zu berechnen.

Wichtige Punkte

• Dynamische Programmierung (DP): Wir verwenden dynamische Programmierung, um die Mindestkosten für jeden Tag im Auge zu behalten.
• Reisetage: Die Angabe der Reisetage erfolgt in streng aufsteigender Reihenfolge, sodass wir genau wissen, an welchen Tagen wir reisen müssen.
• Drei Arten von Pässen: Berechnen Sie für jeden Tag d in der Tagesreihe die Mindestkosten, indem Sie die Kosten für den Kauf eines Passes berücksichtigen, der den aktuellen Tag d abdeckt:
  • 1-Tages-Pass: Die Kosten wären die Kosten für den 1-Tages-Pass (Kosten[0]), addiert zu den Kosten des Vortages (dp[i-1]).
  • 7-Tage-Pass: Die Kosten entsprechen den Kosten für den 7-Tage-Pass (Kosten[1]) zuzüglich der Kosten für den letzten Tag, der innerhalb von 7 Tagen vor dem Tag liegt.
  • 30-Tage-Pass: Die Kosten entsprechen den Kosten für den 30-Tage-Pass (Kosten[2]) zuzüglich der Kosten für den letzten Tag, der innerhalb von 30 Tagen vor dem Tag liegt.
• Basisfall: Die Mindestkosten für einen Tag, an dem keine Reise stattfindet, betragen 0,

Ansatz

1. DP-Array: Wir verwenden ein DP-Array dp[], wobei dp[i] die Mindestkosten darstellt, um alle Reisetage bis zum Tag i abzudecken.
2. Füllen des DP-Arrays: Für jeden Tag von 1 bis 365:
   • Wenn der Tag ein Reisetag ist, berechnen wir die Mindestkosten unter Berücksichtigung von:
     • Die Kosten für die Nutzung einer Tageskarte.
     • Die Kosten für die Nutzung eines 7-Tage-Passes.
     • Die Kosten für die Nutzung eines 30-Tage-Passes.
   • Wenn der Tag kein Reisetag ist, sind die Kosten für diesen Tag die gleichen wie am Vortag (dp[i] = dp[i-1]).
3. Endgültige Antwort: Nach dem Füllen des DP-Arrays werden die Mindestkosten in dp[365] gespeichert, was alle möglichen Reisetage abdeckt.

Planen

1. Initialisieren Sie ein Array dp[] der Größe 366 (ein zusätzliches für die Verarbeitung bis Tag 365).
2. Setzen Sie dp[0] auf 0, da für Tag 0 keine Kosten anfallen.
3. Erstellen Sie eine Reihe von Reisetagen, um schnell zu überprüfen, ob ein bestimmter Tag ein Reisetag ist.
4. Jeden Tag von 1 bis 365 durchlaufen:
   • Wenn es sich um einen Reisetag handelt, berechnen Sie die Mindestkosten unter Berücksichtigung der einzelnen Passtypen.
   • Wenn nicht, übertragen Sie die Kosten vom Vortag.
5. Gibt den Wert bei dp[365] zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 983. Mindestpreis für Tickets

<?php /**
 * @param Integer[] $days
 * @param Integer[] $costs
 * @return Integer
 */
function mincostTickets($days, $costs) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$days1 = [1, 4, 6, 7, 8, 20];
$costs1 = [2, 7, 15];
echo mincostTickets($days1, $costs1); // Output: 11

$days2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs2 = [2, 7, 15];
echo mincostTickets($days2, $costs2); // Output: 17
?>

Erläuterung:

• Der Algorithmus iteriert über jeden Tag des Jahres (365 Tage).
• Für jeden Reisetag werden die Kosten berechnet, indem geprüft wird, ob es günstiger ist:
  • Kaufen Sie eine 1-Tages-Karte (der Preis der 1-Tages-Karte wird zum Preis des Vortages addiert).
  • Kaufen Sie eine 7-Tages-Karte (zusätzlich zu den Kosten der 7-Tages-Karte und unter Berücksichtigung der Reisekosten der letzten 7 Tage).
  • Kaufen Sie eine 30-Tage-Karte (zusätzlich zu den Kosten der 30-Tage-Karte und unter Berücksichtigung der Reisekosten der letzten 30 Tage).
• Wenn es kein Reisetag ist, bleiben die Kosten die gleichen wie am Vortag.

Beispiel-Komplettlösung

Beispiel 1:

Eingabe:

$days = [1, 4, 6, 7, 8, 20];
$costs = [2, 7, 15];

• Tag 1: Kaufen Sie eine Tageskarte für 2 $.
• Tag 4: Kaufen Sie einen 7-Tage-Pass für 7 $ (gilt für die Tage 4 bis 9).
• Tag 20: Kaufen Sie eine weitere 1-Tages-Karte für 2 $.

Gesamtkosten = 2 $, 7 $, 2 $ = 11 $.

Beispiel 2:

Eingabe:

$days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs = [2, 7, 15];

• Tag 1: Kaufen Sie einen 30-Tage-Pass für 15 $ (gilt für die Tage 1 bis 30).
• Tag 31: Kaufen Sie eine 1-Tages-Karte für 2 $.

Gesamtkosten = 15 $ 2 $ = 17 $.

Zeitkomplexität

Die zeitliche Komplexität der Lösung beträgt O(365), da wir alle Tage des Jahres durchlaufen und für jeden Tag konstante Zeitoperationen durchführen (Überprüfung der Reisetage und Aktualisierung des DP). Array). Somit läuft die Lösung in linearer Zeit relativ zur Anzahl der Tage.

Ausgabe zum Beispiel

Beispiel 1:

$days = [1, 4, 6, 7, 8, 20];
$costs = [2, 7, 15];
echo mincostTickets($days, $costs); // Output: 11

Beispiel 2:

$days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs = [2, 7, 15];
echo mincostTickets($days, $costs); // Output: 17

Die Lösung berechnet mithilfe dynamischer Programmierung effizient die Mindestkosten für die Deckung der Reisetage. Durch Iteration über die Tage und Berücksichtigung aller möglichen Pässe (1-Tages-, 7-Tages-, 30-Tages-Pässe) findet der Algorithmus die optimale Strategie für den Kauf der Pässe. Die zeitliche Komplexität ist in Bezug auf die Anzahl der Tage linear und eignet sich daher für die Problembeschrä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 von. Mindestpreis für Tickets. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!