MediumNo. 0983
Minimum Cost For Tickets — LeetCode 983 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- Input
- days = [1,4,6,7,8,20], costs = [2,7,15]
- Output
- 11
- Explanation
- For example, here is one way to buy passes that lets you travel your travel plan:
Python solution
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
@cache
def dfs(i: int) -> int:
if i >= n:
return 0
ans = inf
for c, v in zip(costs, valid):
j = bisect_left(days, days[i] + v)
ans = min(ans, c + dfs(j))
return ans
n = len(days)
valid = [1, 7, 30]
return dfs(0)Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 983. Minimum Cost For Tickets is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0978 | Longest Turbulent Subarray | Medium |
| 0975 | Odd Even Jump | Hard |
| 0045 | Jump Game II | Medium |
| 0053 | Maximum Subarray | Medium |
| 0055 | Jump Game | Medium |
| 0063 | Unique Paths II | Medium |
Frequently asked questions
- How hard is LeetCode 983. Minimum Cost For Tickets?
LeetCode 983. Minimum Cost For Tickets is rated Medium on LeetCode.
- What is the time complexity of LeetCode 983. Minimum Cost For Tickets?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 983. Minimum Cost For Tickets?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 983. Minimum Cost For Tickets cover?
LeetCode 983. Minimum Cost For Tickets is tagged Array and Dynamic Programming on LeetCode.