983. Minimum Cost For Tickets - Explanation

Description

You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.

Train tickets are sold in three different ways:

a 1-day pass is sold for costs[0] dollars,
a 7-day pass is sold for costs[1] dollars, and
a 30-day pass is sold for costs[2] dollars.
The passes allow that many days of consecutive travel.
For example, if we get a *7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

Example 1:

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.

Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]

Output: 17

Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total, you spent $17 and covered all the days of your travel.

Constraints:

1 <= days.length, days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        n = len(days)

        def dfs(i):
            if i == n:
                return 0

            res = costs[0] + dfs(i + 1)
            j = i
            while j < n and days[j] < days[i] + 7:
                j += 1
            res = min(res, costs[1] + dfs(j))

            j = i
            while j < n and days[j] < days[i] + 30:
                j += 1
            res = min(res, costs[2] + dfs(j))

            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(3 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = {}

        def dfs(i):
            if i == len(days):
                return 0
            if i in dp:
                return dp[i]

            dp[i] = float("inf")
            j = i
            for d, c in zip([1, 7, 30], costs):
                while j < len(days) and days[j] < days[i] + d:
                    j += 1
                dp[i] = min(dp[i], c + dfs(j))

            return dp[i]

        return dfs(0)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        n = len(days)
        dp = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            dp[i] = float('inf')
            j = i
            for d, c in zip([1, 7, 30], costs):
                while j < n and days[j] < days[i] + d:
                    j += 1
                dp[i] = min(dp[i], c + dp[j])

        return dp[0]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Bottom-Up) + Two Pointers

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        days.append(days[-1] + 30)
        n = len(days)
        dp = [0] * n
        last7 = last30 = n

        for i in range(n - 2, -1, -1):
            dp[i] = dp[i + 1] + costs[0]

            while last7 > i + 1 and days[last7 - 1] >= days[i] + 7:
                last7 -= 1
            dp[i] = min(dp[i], costs[1] + dp[last7])

            while last30 > i + 1 and days[last30 - 1] >= days[i] + 30:
                last30 -= 1
            dp[i] = min(dp[i], costs[2] + dp[last30])

        return dp[0]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Dynamic Programming (Space Optimized) - I

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp7, dp30 = deque(), deque()
        dp = 0

        for d in days:
            while dp7 and dp7[0][0] + 7 <= d:
                dp7.popleft()

            while dp30 and dp30[0][0] + 30 <= d:
                dp30.popleft()

            dp7.append([d, dp + costs[1]])
            dp30.append([d, dp + costs[2]])
            dp = min(dp + costs[0], dp7[0][1], dp30[0][1])

        return dp

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since we keep at most $30$ values in the queue.

6. Dynamic Programming (Space Optimized) - II

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp7, dp30 = deque(), deque()
        dp = 0

        last7 = last30 = 0
        for i in range(len(days) - 1, -1, -1):
            dp += costs[0]
            while dp7 and dp7[-1][0] >= days[i] + 7:
                last7 = dp7.pop()[1]
            dp = min(dp, costs[1] + last7)

            while dp30 and dp30[-1][0] >= days[i] + 30:
                last30 = dp30.pop()[1]
            dp = min(dp, costs[2] + last30)

            dp7.appendleft([days[i], dp])
            dp30.appendleft([days[i], dp])

        return dp

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since we keep at most $30$ values in the deque.

7. Dynamic Programming (Space Optimized) - III

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = [0] * 366
        i = 0

        for d in range(1, 366):
            dp[d] = dp[d - 1]
            if i == len(days):
                return dp[d]

            if d == days[i]:
                dp[d] += costs[0]
                dp[d] = min(dp[d], costs[1] + dp[max(0, d - 7)])
                dp[d] = min(dp[d], costs[2] + dp[max(0, d - 30)])
                i += 1

        return dp[365]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since the size of the $dp$ array is $366$ .

8. Dynamic Programming (Space Optimized) - IV

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = [0] * 31
        i = 0

        for d in range(1, 366):
            if i >= len(days):
                break

            dp[d % 31] = dp[(d - 1) % 31]

            if d == days[i]:
                dp[d % 31] += costs[0]
                dp[d % 31] = min(dp[d % 31], costs[1] + dp[max(0, d - 7) % 31])
                dp[d % 31] = min(dp[d % 31], costs[2] + dp[max(0, d - 30) % 31])
                i += 1

        return dp[days[-1] % 31]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since the size of the $dp$ array is $31$ .