⚡Flashcard Drill➔
NeetCode #681LC-983Medium1-D Dynamic Programming
← Back to All Problems

#681 · #983 · Minimum Cost For Tickets(最低票价)

📌 Problem Statement & Constraints

You are given days, the days of the year on which you travel, and costs = [cost1, cost7, cost30] for 1-day, 7-day, and 30-day passes. Return the minimum cost to cover all travel days. Constraints: 1 <= days.length <= 365, 1 <= days[i] <= 365 and strictly increasing, 1 <= costs[i] <= 1000.

💡 Core Algorithmic Approaches

  1. Let dp[i] be the minimum cost to cover the first i travel days.
  2. For travel day i, buy a 1-day, 7-day, or 30-day pass; a longer pass covers a contiguous range of travel days.
  3. Find the index of the first travel day covered by the pass and reuse the prefix cost before it: dp[i] = min(dp[i-1] + cost1, dp[j7] + cost7, dp[j30] + cost30).
  4. Because days is sorted, the covered range is found by binary search (or a two-pointer).

💻 Benchmark Python3 Implementation

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        from bisect import bisect_right
        n = len(days)
        dp = [0] * (n + 1)             # dp[i]: cost to cover the first i travel days
        for i in range(1, n + 1):
            d = days[i - 1]
            dp[i] = dp[i - 1] + costs[0]                 # 1-day pass
            j = bisect_right(days, d - 7)                # 7-day pass covers [d, d+6]
            dp[i] = min(dp[i], dp[j] + costs[1])
            k = bisect_right(days, d - 30)               # 30-day pass covers [d, d+29]
            dp[i] = min(dp[i], dp[k] + costs[2])
        return dp[n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): a binary search per day, reducible to O(n) with a two-pointer.
💾 Space Complexity
O(n): the DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating over all 365 calendar days: indexing only the travel days is O(n) and simpler.
  • Using the wrong coverage boundary: a pass bought on day d covers [d, d + 6], so the preceding covered index is the last day below d - 6.
  • Assuming the cheapest per-day pass always wins: longer passes beat short ones across dense travel; the DP explores all three.
  • Believing passes must be bought on travel days: buying on a travel day is sufficient, since any pass can be shifted forward to the first day it covers.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems