. Coût minimum pour les billets

983. Coût minimum pour les billets

Difficulté :Moyen

Sujets :Array, programmation dynamique

Vous avez prévu un voyage en train un an à l'avance. Les jours de l'année au cours desquels vous voyagerez sont indiqués sous forme d'un tableau entier jours. Chaque jour est un nombre entier de 1 à 365.

Les billets de train sont vendus de trois manières différentes :

• un pass 1 jour est vendu au prix de[0] dollars,
• un pass 7 jours est vendu au prix de[1] dollars, et
• un pass 30 jours est vendu au prix de[2] dollars.

Les pass permettent autant de jours de voyage consécutifs.

• Par exemple, si nous obtenons un pass 7 jours le jour 2, alors nous pouvons voyager pendant 7 jours : 2, 3, 4, 5, 6, 7 et 8.

Rendez le nombre minimum de dollars dont vous avez besoin pour voyager chaque jour dans la liste de jours donnée.

Exemple 1 :

• Entrée : jours = [1,4,6,7,8,20], coûts = [2,7,15]
• Sortie : 11
• Explication : Par exemple, voici une façon d'acheter des pass qui vous permettent de voyager conformément à votre projet de voyage :
  • Le premier jour, vous avez acheté un pass d'une journée au coût[0] = 2 $, qui couvrait le premier jour.
  • Le jour 3, vous avez acheté un pass 7 jours au coût[1] = 7 $, qui couvrait les jours 3, 4, ..., 9.
  • Le jour 20, vous avez acheté un pass d'une journée au coût[0] = 2 $, qui couvrait le jour 20.
  • Au total, vous avez dépensé 11 $ et couvert tous les jours de votre voyage.

Exemple 2 :

• Entrée : jours = [1,2,3,4,5,6,7,8,9,10,30,31], coûts = [2,7,15]
• Sortie : 17
• Explication : Par exemple, voici une façon d'acheter des pass qui vous permettent de voyager conformément à votre projet de voyage :
  • Le premier jour, vous avez acheté un pass de 30 jours pour un coût[2] = 15 $ qui couvrait les jours 1, 2, ..., 30.
  • Le jour 31, vous avez acheté un pass d'une journée au coût[0] = 2 $ qui couvrait le jour 31.
  • Au total, vous avez dépensé 17 $ et couvert tous les jours de votre voyage.

Contraintes :

• 1
• 1
• les jours sont dans un ordre strictement croissant.
• coûts.longueur == 3
• 1

Solution :

Le problème consiste à déterminer le coût minimum pour voyager sur un ensemble de jours spécifiés tout au long de l'année. Le problème propose trois types de titres de transport : 1 jour, 7 jours et 30 jours, chacun avec des coûts spécifiques. L’objectif est de trouver le moyen le moins cher de couvrir tous les jours de voyage avec ces pass. La tâche nécessite l'utilisation d'une programmation dynamique pour calculer efficacement le coût minimal.

Points clés

• Programmation dynamique (DP) : Nous utilisons la programmation dynamique pour suivre le coût minimum pour chaque jour.
• Jours de voyage : Les jours de voyage sont indiqués par ordre strictement croissant, ce qui signifie que nous savons exactement quels jours nous devons voyager.
• Trois types de Pass : Pour chaque jour d du tableau jours, calculez le coût minimum en considérant le coût d'achat d'un pass qui couvre le jour d en cours :
  • Pass 1 jour : Le coût serait le coût du pass 1 jour (coûts[0]) ajouté au coût de la journée précédente (dp[i-1]).
  • Pass 7 jours : Le coût serait le coût du pass 7 jours (coûts[1]) ajouté au prix du jour le plus récent qui se situe dans les 7 jours suivant d.
  • Pass 30 jours : Le coût serait le coût du pass 30 jours (coûts[2]) ajouté au coût du jour le plus récent qui se situe dans les 30 jours suivant le jour.
• Cas de base : Le coût minimum pour une journée sans déplacement est de 0.

Approche

1. DP Array : Nous utiliserons un tableau DP dp[] où dp[i] représente le coût minimum pour couvrir tous les jours de voyage jusqu'au jour i.
2. Remplissage du DP Array : Pour chaque jour de 1 à 365 :
   • Si la journée est une journée de voyage, nous calculons le coût minimum en considérant :
     • Le coût d'utilisation d'un pass 1 jour.
     • Le coût d'utilisation d'un pass 7 jours.
     • Le coût d'utilisation d'un pass 30 jours.
   • Si le jour n'est pas un jour de voyage, le coût de ce jour sera le même que celui du jour précédent (dp[i] = dp[i-1]).
3. Réponse finale : Après avoir rempli le tableau DP, le coût minimum sera stocké dans dp[365], qui couvre tous les jours de voyage possibles.

Plan

1. Initialisez un tableau dp[] de taille 366 (un supplémentaire à gérer jusqu'au jour 365).
2. Réglez dp[0] sur 0, car il n'y a aucun frais pour le jour 0.
3. Créez un ensemble travelDays pour vérifier rapidement si un jour particulier est un jour de voyage.
4. Parcourez chaque jour de 1 à 365 :
   • S'il s'agit d'un jour de voyage, calculez le coût minimum en considérant chaque type de pass.
   • Sinon, reportez le coût de la veille.
5. Renvoyer la valeur à dp[365].

Implémentons cette solution en PHP : 983. Coût minimum pour les billets

<?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
?>

Explication:

• L'algorithme itère sur chaque jour de l'année (365 jours).
• Pour chaque jour de voyage, il calcule le coût en considérant s'il est moins cher de :
  • Acheter un pass 1 jour (ajoute le coût du pass 1 jour au coût de la veille).
  • Achetez un pass 7 jours (ajoute le coût du pass 7 jours et prend en compte le coût du voyage au cours des 7 derniers jours).
  • Achetez un pass de 30 jours (ajoute le coût du pass de 30 jours et prend en compte le coût du voyage au cours des 30 derniers jours).
• Si ce n'est pas un jour de voyage, le coût reste le même que la veille.

Exemple de procédure pas à pas

Exemple 1 :

Entrée :

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

• Jour 1 : Achetez un pass 1 jour pour 2 $.
• Jour 4 : Achetez un pass 7 jours pour 7 $ (couvre les jours 4 à 9).
• Jour 20 : Achetez un autre pass d'une journée pour 2 $.

Coût total = 2 $ 7 $ 2 $ = 11 $.

Exemple 2 :

Entrée :

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

• Jour 1 : Achetez un pass de 30 jours pour 15 $ (couvre les jours 1 à 30).
• Jour 31 : Achetez un pass 1 jour pour 2 $.

Coût total = 15 $ 2 $ = 17 $.

Complexité temporelle

La complexité temporelle de la solution est O(365), car nous parcourons tous les jours de l'année, et pour chaque jour, nous effectuons des opérations à temps constant (vérification des jours de voyage et mise à jour du DP tableau). Ainsi, la solution s'exécute en temps linéaire par rapport au nombre de jours.

Sortie par exemple

Exemple 1 :

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

Exemple 2 :

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

La solution calcule efficacement le coût minimum de couverture des jours de voyage grâce à une programmation dynamique. En itérant au fil des jours et en considérant tous les pass possibles (1 jour, 7 jours, 30 jours), l'algorithme trouve la stratégie optimale d'achat des pass. La complexité temporelle est linéaire en termes de nombre de jours, ce qui la rend adaptée aux contraintes du problème.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!