983. Minimum Cost For Tickets
leetcode medium
Task
Вы запланировали несколько поездок на поезде за год вперёд. Дни года, в которые вы будете путешествовать, заданы в виде целочисленного массива days. Каждый день — это целое число от 1 до 365.
Билеты на поезд продаются тремя различными способами:
однодневный билет продаётся за costs[0] долларов,
семидневный билет продаётся за costs[1] долларов, и
тридцатидневный билет продаётся за costs[2] долларов.
Билеты позволяют путешествовать указанное количество дней подряд.
Например, если мы покупаем семидневный билет на 2-й день, то мы можем путешествовать в течение 7 дней: 2, 3, 4, 5, 6, 7 и 8.
Верните минимальное количество долларов, которое вам нужно, чтобы путешествовать каждый день, указанный в списке days.
Пример:
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.
C# solution
matched/originalusing System;
using System.Collections.Generic;
public class Solution {
private HashSet<int> isTravelNeeded = new HashSet<int>();
private int Solve(int[] dp, int[] days, int[] costs, int currDay) {
if (currDay > days[days.Length - 1]) {
return 0;
}
if (!isTravelNeeded.Contains(currDay)) {
return Solve(dp, days, costs, currDay + 1);
}
if (dp[currDay] != -1) {
return dp[currDay];
}
int oneDay = costs[0] + Solve(dp, days, costs, currDay + 1);
int sevenDay = costs[1] + Solve(dp, days, costs, currDay + 7);
int thirtyDay = costs[2] + Solve(dp, days, costs, currDay + 30);
dp[currDay] = Math.Min(oneDay, Math.Min(sevenDay, thirtyDay));
return dp[currDay];
}
public int MincostTickets(int[] days, int[] costs) {
int lastDay = days[days.Length - 1];
int[] dp = new int[lastDay + 1];
for (int i = 0; i <= lastDay; i++) {
dp[i] = -1;
}
foreach (int day in days) {
isTravelNeeded.Add(day);
}
return Solve(dp, days, costs, 1);
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private HashSet<int> isTravelNeeded = new HashSet<int>();
private int Solve(vector<int>& dp, vector<int>& days, vector<int>& costs, int currDay) {
if (currDay > days[days.size() - 1]) {
return 0;
}
if (!isTravelNeeded.Contains(currDay)) {
return Solve(dp, days, costs, currDay + 1);
}
if (dp[currDay] != -1) {
return dp[currDay];
}
int oneDay = costs[0] + Solve(dp, days, costs, currDay + 1);
int sevenDay = costs[1] + Solve(dp, days, costs, currDay + 7);
int thirtyDay = costs[2] + Solve(dp, days, costs, currDay + 30);
dp[currDay] = min(oneDay, min(sevenDay, thirtyDay));
return dp[currDay];
}
public int MincostTickets(vector<int>& days, vector<int>& costs) {
int lastDay = days[days.size() - 1];
vector<int>& dp = new int[lastDay + 1];
for (int i = 0; i <= lastDay; i++) {
dp[i] = -1;
}
foreach (int day in days) {
isTravelNeeded.push_back(day);
}
return Solve(dp, days, costs, 1);
}
}Java solution
matched/originalimport java.util.HashSet;
import java.util.Set;
class Solution {
private Set<Integer> isTravelNeeded = new HashSet<>();
private int solve(int[] dp, int[] days, int[] costs, int currDay) {
if (currDay > days[days.length - 1]) {
return 0;
}
if (!isTravelNeeded.contains(currDay)) {
return solve(dp, days, costs, currDay + 1);
}
if (dp[currDay] != -1) {
return dp[currDay];
}
int oneDay = costs[0] + solve(dp, days, costs, currDay + 1);
int sevenDay = costs[1] + solve(dp, days, costs, currDay + 7);
int thirtyDay = costs[2] + solve(dp, days, costs, currDay + 30);
dp[currDay] = Math.min(oneDay, Math.min(sevenDay, thirtyDay));
return dp[currDay];
}
public int mincostTickets(int[] days, int[] costs) {
int lastDay = days[days.length - 1];
int[] dp = new int[lastDay + 1];
for (int i = 0; i <= lastDay; i++) {
dp[i] = -1;
}
for (int day : days) {
isTravelNeeded.add(day);
}
return solve(dp, days, costs, 1);
}
}JavaScript solution
matched/originalclass Solution {
constructor() {
this.isTravelNeeded = new Set();
}
solve(dp, days, costs, currDay) {
if (currDay > days[days.length - 1]) {
return 0;
}
if (!this.isTravelNeeded.has(currDay)) {
return this.solve(dp, days, costs, currDay + 1);
}
if (dp[currDay] != -1) {
return dp[currDay];
}
let oneDay = costs[0] + this.solve(dp, days, costs, currDay + 1);
let sevenDay = costs[1] + this.solve(dp, days, costs, currDay + 7);
let thirtyDay = costs[2] + this.solve(dp, days, costs, currDay + 30);
dp[currDay] = Math.min(oneDay, Math.min(sevenDay, thirtyDay));
return dp[currDay];
}
mincostTickets(days, costs) {
let lastDay = days[days.length - 1];
let dp = new Array(lastDay + 1).fill(-1);
for (let day of days) {
this.isTravelNeeded.add(day);
}
return this.solve(dp, days, costs, 1);
}
}Python solution
matched/originalclass Solution:
def __init__(self):
self.isTravelNeeded = set()
def solve(self, dp, days, costs, currDay):
if currDay > days[-1]:
return 0
if currDay not in self.isTravelNeeded:
return self.solve(dp, days, costs, currDay + 1)
if dp[currDay] != -1:
return dp[currDay]
oneDay = costs[0] + self.solve(dp, days, costs, currDay + 1)
sevenDay = costs[1] + self.solve(dp, days, costs, currDay + 7)
thirtyDay = costs[2] + self.solve(dp, days, costs, currDay + 30)
dp[currDay] = min(oneDay, min(sevenDay, thirtyDay))
return dp[currDay]
def mincostTickets(self, days, costs):
lastDay = days[-1]
dp = [-1] * (lastDay + 1)
for day in days:
self.isTravelNeeded.add(day)
return self.solve(dp, days, costs, 1)Go solution
matched/originalpackage main
import "math"
type Solution struct {
isTravelNeeded map[int]bool
}
func (s *Solution) solve(dp []int, days []int, costs []int, currDay int) int {
if currDay > days[len(days)-1] {
return 0
}
if !s.isTravelNeeded[currDay] {
return s.solve(dp, days, costs, currDay+1)
}
if dp[currDay] != -1 {
return dp[currDay]
}
oneDay := costs[0] + s.solve(dp, days, costs, currDay+1)
sevenDay := costs[1] + s.solve(dp, days, costs, currDay+7)
thirtyDay := costs[2] + s.solve(dp, days, costs, currDay+30)
dp[currDay] = int(math.Min(float64(oneDay), math.Min(float64(sevenDay), float64(thirtyDay))))
return dp[currDay]
}
func (s *Solution) MincostTickets(days []int, costs []int) int {
lastDay := days[len(days)-1]
dp := make([]int, lastDay+1)
for i := range dp {
dp[i] = -1
}
s.isTravelNeeded = make(map[int]bool)
for _, day := range days {
s.isTravelNeeded[day] = true
}
return s.solve(dp, days, costs, 1)
}Explanation
Algorithm
Создайте массив dp размером на один больше последнего дня, в который нужно путешествовать. Инициализируйте все значения -1, что означает, что ответ для этого дня ещё не был вычислен. Также создайте хэш-набор isTravelNeeded из days.
Создайте функцию solve, которая принимает аргумент currDay. Если currDay больше последнего дня, когда нужно путешествовать, просто верните 0, так как все дни уже покрыты. Если currDay отсутствует в isTravelNeeded, перейдите к currDay + 1. Если ответ для currDay в массиве dp не равен -1, это означает, что ответ уже был вычислен, поэтому просто верните его.
Найдите стоимость трёх билетов, которые можно использовать в этот день, добавьте соответствующую стоимость и обновите dp[currDay] соответственно в рекурсивном вызове. Вызовите solve, передав currDay = 1, и верните ответ.
😎