MEDIUM 1-D Dynamic Programming

983. Minimum Cost For Tickets

📖 Problem

You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365. Train tickets are sold in three different ways: - A 1-day pass is sold for costs[0] dollars - A 7-day pass is sold for costs[1] dollars - A 30-day pass is sold for costs[2] dollars The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8. Return the minimum number of dollars you need to travel every day in the given list of days.

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •Array DP table updates
  • •State transition thinking
  • •Base case initialization

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply Dynamic Programming reasoning pattern

💡 Approach

  • → Use DP where dp[i] = min cost to travel up to day i
  • → For each day, consider buying 1, 7, or 30 day pass
  • → If not a travel day, cost is same as previous day
  • → Time: O(365), Space: O(365) which is effectively O(1)

🧭 Prerequisites

#377 Combination Sum IV #946 Distinct Substrings (LeetCode 1698)

🛠️ Hints & Pitfalls

Hints

  • •Use DP where dp[i] = min cost to travel up to day i
  • •For each day, consider buying 1, 7, or 30 day pass
  • •If not a travel day, cost is same as previous day

Common Pitfalls

  • •Time: O(365), Space: O(365) which is effectively O(1)

🧪 Test Cases

Test Case 1
Not run
Input:
mincostTickets([1,4,6,7,8,20], [2,7,15]);
Expected:
null
Test Case 2
Not run
Input:
mincostTickets([1,2,3,4,5,6,7,8,9,10,30,31], [2,7,15]);
Expected:
null
Test Case 3
Not run
Input:
mincostTickets(days: number[], costs: number[]);
Expected:
Computed from hidden reference

📝 Code Editor

📚 Reference Solution

▼

🔗 Related Problems

#70 Climbing Stairs #97 Interleaving String #123 Best Time to Buy and Sell Stock III #279 Perfect Squares #377 Combination Sum IV
⌘K Search ⌘↩ Run ⌘S Submit