https://leetcode.com/problems/minimum-cost-for-tickets

There are a lot of different dp solution, which have O(days) complexity, which is in fact O(30*days), so it depeneds a lot on our numbers [1,7,30]. My solution is universal: you can choose any passes you want, and time complexity will not depend on them. Let me introduce my notations:

  1. k is number of passes and P is durations of these passes, in our case it is [1,7,30]; cost is minimal cost so far, in the beginning it is equal to 0.
  2. Q is list of k queues. Why we need queues? When we want to find the best cost we can have at some day d, we need to look back 30 days before, so why not keep all these period in queue? What we keep in this queue? We keep pairs [day, cost]. Also we have queue for 7 day pass and for 1 day pass.

Let us go through example for better understanding: days = [1,4,6,7,8,20], costs = [2,7,15].

  1. day = 1, Q[0] = [[1,2]], Q[1] = [[1,7]], Q[2] = [[1, 15]]: for the first day we put it in all three queues.
  2. day = 4, Q[0] = [[4,4]], Q[1] = [[1,7], [4,9]], Q[2] = [[1,15], [4,17]]: we update Q[0], also Q[1] and Q[2] now have two elements.
  3. day = 6, Q[0] = [[6,6]], Q[1] = [[1,7], [4, 9], [6,11]], Q[2] = [[1,15], [4,17], [6,19]]: update Q[0], add element to Q[1] and Q[2].
  4. day = 7, Q[0] = [[7,8]], Q[1] = [[1,7], [4,9], [6,11], [7,13]], Q[2] = [[1,15], [4,17], [6,19], [7,21]], similar logic.
  5. day = 8, Q[0] = [[8,9]], Q[1] = [[4,9], [6,11], [7,13], [8,14]], Q[2] = [[1,15], [4,17], [6,19], [7,21], [8,22]]: update Q[0], also add element to the end of Q[1] and remove element from the beginning of Q[1], because it is outdated.
  6. day = 20, Q[0] = [[20,11]], Q[1] = [[20,16]], Q[2] = [[1,15], [4,17], [6,19], [7,21], [8,22], [20,24]].

So, we iterate through our days and update our queues on each step. Then we choose minimum possible result.

Complexity: time complexity is O(days), length of days list, because we process each element at most 3 times: we can put and remove it to each queue only once. For general case complexity is O(days * k). Space complexity is O(30+7+1) in our case and O(sum(P)) in general case.

class Solution:
    def mincostTickets(self, days, costs):
        k, P, cost = 3, [1,7,30], 0
        Q = [deque() for _ in range(k)]

        for d in days:
            for i in range(k):
                while Q[i] and Q[i][0][0] + P[i] <= d: Q[i].popleft()
                Q[i].append([d, cost + costs[i]])
         
            cost = min([Q[i][0][1] for i in range(k)])

        return cost

Remark I think this problem is similar to problem 264. Ugly Number II, there we also need to keep several candidates for new number and update them.

If you like the solution, you can upvote it on leetcode discussion section: Problem 0983