983. Coût minimum des billets

983. Coût minimum des billets

Difficulté : moyenne

Sujets :Tableau,Programmation dynamique

Vous avez prévu un voyage en train un an à l'avance. Les jours de l'année pendant lesquels vous voyagerez sont donnés sous forme de tableau entierjours. Chaque jour est un entier de1à365.

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

• un pass 1 jour est vendu pourcoûts[0]dollars,
• un pass 7 jours est vendu pourcoûts[1]dollars, et
• un pass 30 jours est vendu pourcoûts[2]dollars.

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

• Par exemple, si nous obtenons un pass 7 jours le jour2, alors nous pourrons voyager pendant7jours:2,3,4,5,6,7, et8.

Renvoyez 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 selon votre projet de voyage :
  • Le premier jour, vous avez acheté un pass d'une journée au prix de [0] = 2 $, qui couvrait le premier jour.
  • Le troisième jour, vous avez acheté un pass de 7 jours au coût[1] = 7 $, qui couvrait les jours 3, 4, ... et 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...
  [Courte citation de 8% de l'article original]