# 31.12.2024 [983. Minimum Cost For Tickets]
Min sum buying 1,7,30-days tickets to travel all days #medium #dymanic_programming
31.12.2024
983. Minimum Cost For Tickets medium blog post youtube deep-dive
Join me on Telegram
Problem TLDR
Min sum buying 1,7,30-days tickets to travel all days #medium #dymanic_programming
Intuition
Observing the data:
// 1,2,3,4,5,6,7,8,9,10,29,30,31 2 7 15
// * . +2
// * . +2 4
// * . +2 6
// * . +2 8 vs 7, take 7,
// . from = max(1, 4-7)
// . . . to = from+7
// * +2 9
// * +2 11
// * +2 13
we can retrospectively switch previous ticket from
1
-day to7
day or30
days if it is less expensive (this is a cleverer solution and requires clever implementation, so initially I've dropped this idea)the tail (or the head) is independent and can be calculated separately, meaning, we can do a full Depth-First search and cache the result
Approach
top-down DFS is easier to reason about: do choices, choose the best, then add caching
then rewrite to bottom-up, reverse iteration order for CPU cache speed
the idea of retrospectively replacing the 1-day ticket for 7 or 30-day can be written with queues of 7-day and 30-day ticket results: pop expired from the front, add current to the tail, the best results are at the front (c++ solution)
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(n)$$, O(1) for queues, as only the last 30 days are considered
Code
val dp = HashMap<Int, Int>()
fun mincostTickets(days: IntArray, costs: IntArray, start: Int = 0): Int =
if (start < days.size) dp.getOrPut(start) {
var i = start
costs.zip(listOf(1, 7, 30)).minOf { (c, d) ->
while (i < days.size && days[i] - days[start] < d) ++i
c + mincostTickets(days, costs, i)
}
} else 0
pub fn mincost_tickets(days: Vec<i32>, costs: Vec<i32>) -> i32 {
let mut dp = vec![i32::MAX; days.len() + 1]; dp[0] = 0;
for start in 0..days.len() {
let mut i = start;
for (c, d) in costs.iter().zip([1, 7, 30]) {
while i < days.len() && days[i] - days[start] < d { i += 1 }
dp[i] = dp[i].min(dp[start] + c)
}
}; dp[days.len()]
}
int mincostTickets(vector<int>& days, vector<int>& costs) {
queue<pair<int, int>> last7, last30; int res = 0;
for (auto d: days) {
while (last7.size() && last7.front().first + 7 <= d) last7.pop();
while (last30.size() && last30.front().first + 30 <= d) last30.pop();
last7.push({d, res + costs[1]});
last30.push({d, res + costs[2]});
res = min({res + costs[0], last7.front().second, last30.front().second});
} return res;
}