▲

3

▼

🚄 Минимизируем затраты на поездки с помощью ДП и техники скользящего окна 🚀

leetcoder, 31-12-2024 , 281

Последняя в уходящем году задача 983. Minimum Cost For Tickets требует от нас несложного сочетания техник динамического программирования и скользящего окна.

📜 Условие задачи

У вас есть запланированные дни поездок в течение года, указанные в массиве days. Билеты можно приобрести по следующим ценам:

• Однодневный билет за costs[0] долларов.
• Семидневный билет (покрывает любые последовательно идущие 7 дней) за costs[1] долларов.
• Тридцатидневный билет (покрывает любые последовательно идущие 30 дней) за costs[2] долларов.

Необходимо определить минимальные затраты, чтобы покрыть все дни из списка days.

💡 Идея

Для минимизации затрат можно использовать динамическое программирование.
Основная идея — поочередно вычислять минимальную стоимость для каждой даты из массива days, учитывая разные виды билетов, а также использовать индексы скользящих окон для эффективного вычисления диапазонов покрытия билетов.

🛠️ Детали подхода

1. Создаем массив dp, где dp[i] хранит минимальную стоимость поездок для первых i дней.
2. Используем два указателя last7_index и last30_index для отслеживания начала диапазона дней, покрываемых 7-дневным и 30-дневным билетами.
3. Для каждого дня:
   • Обновляем указатели, чтобы определить, с какого индекса можно покрыть день текущим билетом.
   • Рассчитываем минимальную стоимость, сравнивая три возможных варианта: покупка 1-дневного, 7-дневного и 30-дневного билетов.
4. Возвращаем последнее значение из массива dp, которое представляет минимальную стоимость для всех поездок.

📊 Асимптотика

• Временная сложность: O(n), где n — количество дней в массиве days.
  • Каждый указатель (last7_index, last30_index) обновляется не более одного раза на каждый день.
• Пространственная сложность: O(n)
  • для хранения массива dp.

📜 Код

impl Solution {
    pub fn mincost_tickets(days: Vec<i32>, costs: Vec<i32>) -> i32 {
        // Dynamic programming array to store minimum costs for each day in `days`
        let n = days.len();
        let mut dp = vec![0; n + 1]; // dp[i] is the minimum cost to cover days[0..i-1]
        let mut last7_index = 0; // Pointer for the last valid day for a 7-day pass
        let mut last30_index = 0; // Pointer for the last valid day for a 30-day pass

        for i in 0..n {
            // Update the pointer for the last valid day covered by a 7-day pass
            while days[last7_index] <= days[i] - 7 {
                last7_index += 1;
            }
            // Update the pointer for the last valid day covered by a 30-day pass
            while days[last30_index] <= days[i] - 30 {
                last30_index += 1;
            }

            // Calculate the minimum cost for the current day
            dp[i + 1] = dp[i] + costs[0]; // Cost with a 1-day pass
            dp[i + 1] = dp[i + 1].min(dp[last7_index] + costs[1]); // Cost with a 7-day pass
            dp[i + 1] = dp[i + 1].min(dp[last30_index] + costs[2]); // Cost with a 30-day pass
        }

        // Return the total minimum cost to cover all travel days
        dp[n]
    }
}