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
- Let
dp[i]be the minimum cost to cover the firstitravel days. - For travel day
i, buy a 1-day, 7-day, or 30-day pass; a longer pass covers a contiguous range of travel days. - 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). - Because
daysis 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
dcovers[d, d + 6], so the preceding covered index is the last day belowd - 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.