983. Minimum Cost For Tickets

MediumView on LeetCode

Array Dynamic Programming

Time: O(n)

Space: O(n)

Intuition

DP over days. Non-travel days cost equals previous day. Travel days take minimum of 1-day, 7-day, 30-day pass options.

Algorithm

1Travel day set. dp[d] = min cost through day d.
2Non-travel day: dp[d] = dp[d-1].
3Travel day: dp[d] = min(dp[d-1]+cost[0], dp[max(0,d-7)]+cost[1], dp[max(0,d-30)]+cost[2]).

Common Pitfalls

•Iterate over calendar days (1 to max travel day), not just travel day indices.

983.cs

// Approach: Greedy DP with two sliding queues for 7-day and 30-day windows; for each travel day pick the cheapest option.
// Time: O(n) Space: O(n)

public class Solution
{
    public int MincostTickets(int[] days, int[] costs)
    {
        int ans = 0;
        Queue<KeyValuePair<int, int>> last7 = new Queue<KeyValuePair<int, int>>(); // [day, cost]
        Queue<KeyValuePair<int, int>> last30 = new Queue<KeyValuePair<int, int>>();

        foreach (var day in days)
        {
            while (last7.Count > 0 && last7.Peek().Key + 7 <= day)
                last7.Dequeue();
            while (last30.Count > 0 && last30.Peek().Key + 30 <= day)
                last30.Dequeue();
            last7.Enqueue(new KeyValuePair<int, int>(day, ans + costs[1]));
            last30.Enqueue(new KeyValuePair<int, int>(day, ans + costs[2]));
            ans = Math.Min(ans + costs[0], Math.Min(last7.Count > 0 ? last7.Peek().Value : int.MaxValue, last30.Count > 0 ? last30.Peek().Value : int.MaxValue));
        }

        return ans;
    }
}

Was this solution helpful?