Задача: 983. Minimum Cost For Tickets
Сложность: medium

Вы запланировали несколько поездок на поезде за год вперёд. Дни года, в которые вы будете путешествовать, заданы в виде целочисленного массива 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.

👨‍💻 Алгоритм:

1⃣Создайте массив dp размером на один больше последнего дня, в который нужно путешествовать. Инициализируйте все значения -1, что означает, что ответ для этого дня ещё не был вычислен. Также создайте хэш-набор isTravelNeeded из days.

2⃣Создайте функцию solve, которая принимает аргумент currDay. Если currDay больше последнего дня, когда нужно путешествовать, просто верните 0, так как все дни уже покрыты. Если currDay отсутствует в isTravelNeeded, перейдите к currDay + 1. Если ответ для currDay в массиве dp не равен -1, это означает, что ответ уже был вычислен, поэтому просто верните его.

3⃣Найдите стоимость трёх билетов, которые можно использовать в этот день, добавьте соответствующую стоимость и обновите dp[currDay] соответственно в рекурсивном вызове. Вызовите solve, передав currDay = 1, и верните ответ.

😎 Решение:

class Solution {
    private val isTravelNeeded = mutableSetOf<Int>()

    private fun solve(dp: IntArray, days: IntArray, costs: IntArray, currDay: Int): Int {
        if (currDay > days.last()) {
            return 0
        }
        
        if (currDay !in isTravelNeeded) {
            return solve(dp, days, costs, currDay + 1)
        }
        
        if (dp[currDay] != -1) {
            return dp[currDay]
        }
        
        val oneDay = costs[0] + solve(dp, days, costs, currDay + 1)
        val sevenDay = costs[1] + solve(dp, days, costs, currDay + 7)
        val thirtyDay = costs[2] + solve(dp, days, costs, currDay + 30)
        
        dp[currDay] = minOf(oneDay, minOf(sevenDay, thirtyDay))
        return dp[currDay]
    }

    fun mincostTickets(days: IntArray, costs: IntArray): Int {
        val lastDay = days.last()
        val dp = IntArray(lastDay + 1) { -1 }
        
        for (day in days) {
            isTravelNeeded.add(day)
        }
        
        return solve(dp, days, costs, 1)
    }
}

Ставь 👍 и забирай 📚 Базу знаний