Minimum Cost For Tickets

How it works

The previous approach uses 366 slots, but we only ever look back at most 30 days. By using modular arithmetic with a size-31 array, we can reduce space to constant while still accessing the necessary previous states. The index d % 31 ensures we have access to all values within the 30-day window.

Steps

1. Create a DP array of size 31.
2. For each calendar day, use modular indexing d % 31.
3. For non-travel days, copy from (d - 1) % 31.
4. For travel days, compute the minimum using modular indices for lookback.
5. Return dp[last_travel_day % 31].

Complexity

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

Things to watch for

Misunderstanding Pass Duration Coverage

A 7-day pass bought on day d covers days d through d+6 (inclusive), not d+1 through d+7. Similarly, a 30-day pass covers days d through d+29. When finding the next uncovered day, check if days[j] < days[i] + duration, not days[j] <= days[i] + duration. This off-by-one error leads to passes covering one fewer day than they should.

Not Considering All Three Pass Options at Each Decision Point

At each travel day, you must consider all three pass types: 1-day, 7-day, and 30-day. Some solutions greedily choose based on the number of upcoming travel days, but this can be suboptimal. For example, a 7-day pass might be cheaper than seven 1-day passes even if you only travel twice in that week. Always compute and compare the cost of all three options.

Incorrect Base Case or Boundary Handling

When using bottom-up DP, ensure dp[n] = 0 (no cost needed after all travel days). When looking back for pass coverage (e.g., dp[max(0, d-7)]), handle negative indices by clamping to 0. Failing to properly initialize boundaries or handle edge cases like single-day trips or consecutive travel days can produce incorrect results.

from typing import List

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]

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> dp(31, 0);
        int i = 0;

        for (int d = 1; d <= 365; d++) {
            if (i >= days.size()) 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++;
            }
        }

        return dp[days.back() % 31];
    }
};