Thomas Ngo

Software Engineer

3 minute read

Problem Statement

problem

Intuition

When I first encountered this problem, I immediately recognized that it revolves around minimizing costs over a timeline of travel days. Since we have three different types of tickets (daily, weekly, and monthly), the challenge is essentially choosing the most cost-effective combination while covering all the given travel days. I noticed that this has the flavor of a dynamic programming problem due to overlapping subproblems and an optimal substructure.

Approach

To solve this problem, I decided to use a recursive Depth-First Search (DFS) approach combined with memoization to store and reuse results of previously computed states.

Here’s the plan:

  1. Sort the travel days: Although not strictly necessary here, sorting helps conceptualize the problem more clearly.
  2. Use a set for quick lookups: I used a set for the travel days to efficiently determine if a given day requires a ticket.
  3. Recursive DFS with memoization: The recursion function attempts to calculate the minimum cost starting from any given day. If the current day is not a travel day, it skips to the next day without adding to the cost. Otherwise, it considers all three ticket options (daily, weekly, monthly) and takes the minimum of these costs.

Key Details:

  • Base Case: If the start day exceeds the last travel day, the recursion returns the accumulated cost as no further tickets are needed.
  • Memoization: To avoid redundant computations, I stored results of subproblems in a dictionary using (start, curr_cost) as the key.

Complexity

  • Time Complexity:
    The complexity is approximately \(O(n \cdot d)\), where \(n\) is the number of days in the travel list, and \(d\) is the maximum gap between travel days. This is because the recursion runs for each travel day and explores at most 3 options per recursive step.
  • Space Complexity:
    \(O(n)\) for the memoization dictionary and the recursion stack.

Code

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        res = float('inf')
        days.sort()
        travel_days = set(days)
        last_day = max(days)

        def dfs(start, curr_cost):
            if start > last_day:
                return curr_cost

            if start not in travel_days:
                return dfs(start + 1, curr_cost)

            if (start, curr_cost) in memo:
                return memo[(start, curr_cost)]

            ans = float('inf')
            ans = min(ans, dfs(start + 1, curr_cost + costs[0]))
            ans = min(ans, dfs(start + 7, curr_cost + costs[1]))
            ans = min(ans, dfs(start + 30, curr_cost + costs[2]))
            memo[(start, curr_cost)] = ans
            return ans

        memo = defaultdict(int)
        return dfs(0, 0)

Editorial

Approach 1: Top-Down Dynamic Programming

class Solution {
public:
    unordered_set<int> isTravelNeeded;

    int solve(vector<int>& dp, vector<int>& days, vector<int>& costs, int currDay) {
        // If we have iterated over travel days, return 0.
        if (currDay > days[days.size() - 1]) {
            return 0;
        }

        // If we don't need to travel on this day, move on to next day.
        if (isTravelNeeded.find(currDay) == isTravelNeeded.end()) {
            return solve(dp, days, costs, currDay + 1);
        }

        // If already calculated, return from here with the stored answer.
        if (dp[currDay] != -1) {
            return dp[currDay];
        }

        int oneDay = costs[0] + solve(dp, days, costs, currDay + 1);
        int sevenDay = costs[1] + solve(dp, days, costs, currDay + 7);
        int thirtyDay = costs[2] + solve(dp, days, costs, currDay + 30);

        // Store the cost with the minimum of the three options.
        return dp[currDay] = min(oneDay, min(sevenDay, thirtyDay));
    }

    int mincostTickets(vector<int>& days, vector<int>& costs) {
        // The last day on which we need to travel.
        int lastDay = days[days.size() - 1];
        vector<int> dp(lastDay + 1, -1);

        // Mark the days on which we need to travel.
        for (int day : days) {
            isTravelNeeded.insert(day);
        }

        return solve(dp, days, costs, 1);
    }
};

Approach 2: Bottom-up Dynamic Programming

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int lastDay = days[days.size() - 1];
        vector<int> dp(lastDay + 1, 0);

        int i = 0;
        for (int day = 1; day <= lastDay; day++) {
            if (day < days[i]) {
                dp[day] = dp[day - 1];
            } else {
                i++;
                dp[day] = min({dp[day - 1] + costs[0],
                               dp[max(0, day - 7)] + costs[1],
                               dp[max(0, day - 30)] + costs[2]});
            }
        }

        return dp[lastDay];
    }
};
  • time: O(K) where k is the size of the array
  • space: O(K)

You may also enjoy