Minimum Cost for Tickets
Last updated
Last updated
On day i
, if there is an existing ticket covering today, then there is no need to buy any more
On day i
, if there are not existing tickets covering today, then we can try buying all three kinds of tickets
A part of the transitions involves keeping track of the duration of the ticket bought.
Modelling the transitions, we get:
The recurrence relation is:
If we intend to buy a ticket on day i
, we cannot be under an existing ticket. So we have to look backwards by (1/7/30) days to find the last time that ticket was bought.
To determine what's the cheapest, we would simply pick the cheapest among the three possible choices when we are looking back.
Hence, the following recurrence relation:
Where we would be trying to buy all types of tickets whenever we aren't being covered by a ticket. However, this means that we are trying about possibilities. While memoization can help, it may be better to try reducing the trial-and-error.
Given days , what is the minimum cost to travel on day i
?
If we aren't going to travel on day i
, then we should not try purchasing a ticket, and instead defer the computation via .