Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/983.html
983. Minimum Cost For Tickets (Medium)
In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days
. Each day is an integer from 1
to 365
.
Train tickets are sold in 3 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: day 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
.
Example 1:
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: On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1. On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9. On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20. In total you spent $11 and covered all the days of your travel.
Example 2:
Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15] Output: 17 Explanation: For example, here is one way to buy passes that lets you travel your travel plan: On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30. On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31. In total you spent $17 and covered all the days of your travel.
Note:
1 <= days.length <= 365
1 <= days[i] <= 365
days
is in strictly increasing order.costs.length == 3
1 <= costs[i] <= 1000
Related Topics:
Dynamic Programming
Similar Questions:
Solution 1. DP Top-down
// OJ: https://leetcode.com/problems/minimum-cost-for-tickets/
// Time: O(N)
// Space: O(N)
class Solution {
vector<int> m;
int dp(vector<int> &days, vector<int>& costs, int i) {
int N = days.size();
if (i == N) return 0;
if (m[i] != INT_MAX) return m[i];
int ans = dp(days, costs, i + 1) + costs[0], j = i;
while (j < N && days[j] < days[i] + 7) ++j;
ans = min(ans, dp(days, costs, j) + costs[1]);
while (j < N && days[j] < days[i] + 30) ++j;
ans = min(ans, dp(days, costs, j) + costs[2]);
return m[i] = ans;
}
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
m.assign(days.size(), INT_MAX);
return dp(days, costs, 0);
}
};
Solution 2. DP Bottom-up
// OJ: https://leetcode.com/problems/minimum-cost-for-tickets/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
int N = days.size();
vector<int> dp(N + 1);
for (int i = N - 1; i >= 0; --i) {
dp[i] = min({ dp[i + 1] + costs[0],
dp[lower_bound(begin(days) + i, end(days), days[i] + 7) - begin(days)] + costs[1],
dp[lower_bound(begin(days) + i, end(days), days[i] + 30) - begin(days)] + costs[2] });
}
return dp[0];
}
};
Another version which is from left to right and push the data to the next state.
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
int N = days.size();
vector<int> dp(N + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i < N; ++i) {
dp[i + 1] = min(dp[i + 1], dp[i] + costs[0]);
for (int j = 1; j < 3; ++j) {
int d = j == 1 ? 7 : 30;
int k = lower_bound(begin(days), end(days), days[i] + d) - begin(days);
dp[k] = min(dp[k], dp[i] + costs[j]);
}
}
return dp[N];
}
};
-
class Solution { public int mincostTickets(int[] days, int[] costs) { int[] intervals = {1, 7, 30}; int length = days.length; int minDay = days[0], maxDay = days[length - 1]; Set<Integer> daysSet = new HashSet<Integer>(); for (int day : days) daysSet.add(day); int[][] dp = new int[maxDay + 1][4]; for (int i = minDay; i <= maxDay; i++) { for (int j = 0; j < 4; j++) dp[i][j] = Integer.MAX_VALUE; } for (int i = minDay; i <= maxDay; i++) { int prevMin = min(dp[i - 1]); if (daysSet.contains(i)) { for (int j = 0; j < 3; j++) { int intervalEnd = Math.min(i + intervals[j] - 1, maxDay); int totalCost = prevMin + costs[j]; dp[i][j] = totalCost; for (int k = i + 1; k <= intervalEnd; k++) dp[k][3] = Math.min(dp[k][3], totalCost); } } else { for (int j = 0; j < 3; j++) dp[i][j] = prevMin + costs[j]; dp[i][3] = Math.min(dp[i][3], prevMin); } } return min(dp[maxDay]); } public int min(int[] array) { int min = Integer.MAX_VALUE; for (int num : array) min = Math.min(min, num); return min; } } ############ class Solution { private static final int[] T = new int[] {1, 7, 30}; private int[] costs; private int[] days; private int[] f; private int n; public int mincostTickets(int[] days, int[] costs) { n = days.length; f = new int[n]; this.costs = costs; this.days = days; Arrays.fill(f, -1); return dfs(0); } private int dfs(int i) { if (i >= n) { return 0; } if (f[i] != -1) { return f[i]; } int res = Integer.MAX_VALUE; for (int k = 0; k < 3; ++k) { int j = lowerBound(days, days[i] + T[k]); res = Math.min(res, costs[k] + dfs(j)); } f[i] = res; return res; } private int lowerBound(int[] days, int x) { int left = 0, right = days.length; while (left < right) { int mid = (left + right) >> 1; if (days[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; } }
-
// OJ: https://leetcode.com/problems/minimum-cost-for-tickets/ // Time: O(N) // Space: O(N) class Solution { vector<int> m; int dp(vector<int> &days, vector<int>& costs, int i) { int N = days.size(); if (i == N) return 0; if (m[i] != INT_MAX) return m[i]; int ans = dp(days, costs, i + 1) + costs[0], j = i; while (j < N && days[j] < days[i] + 7) ++j; ans = min(ans, dp(days, costs, j) + costs[1]); while (j < N && days[j] < days[i] + 30) ++j; ans = min(ans, dp(days, costs, j) + costs[2]); return m[i] = ans; } public: int mincostTickets(vector<int>& days, vector<int>& costs) { m.assign(days.size(), INT_MAX); return dp(days, costs, 0); } };
-
class Solution: def mincostTickets(self, days: List[int], costs: List[int]) -> int: @cache def dfs(i): if i >= len(days): return 0 res = inf for c, d in zip(costs, [1, 7, 30]): j = bisect_left(days, days[i] + d) res = min(res, c + dfs(j)) return res return dfs(0) ############ class Solution(object): def mincostTickets(self, days, costs): """ :type days: List[int] :type costs: List[int] :rtype: int """ dp = [float("inf")] * 366 for day in days: dp[day] = 0 dp[0] = 0 for i in range(1, 366): if dp[i] == float("inf"): dp[i] = dp[i - 1] else: cur = dp[i - 1] + costs[0] cur = min(dp[max(0, i - 7)] + costs[1], cur) cur = min(dp[max(0, i - 30)] + costs[2], cur) dp[i] = cur return dp[days[-1]]
-
func mincostTickets(days []int, costs []int) int { t := []int{1, 7, 30} n := len(days) f := make([]int, n) for i := range f { f[i] = -1 } var dfs func(i int) int dfs = func(i int) int { if i >= n { return 0 } if f[i] != -1 { return f[i] } res := 0x3f3f3f3f for k, c := range costs { j := lowerBound(days, days[i]+t[k]) res = min(res, c+dfs(j)) } f[i] = res return res } return dfs(0) } func lowerBound(arr []int, x int) int { left, right := 0, len(arr) for left < right { mid := (left + right) >> 1 if arr[mid] >= x { right = mid } else { left = mid + 1 } } return left } func min(a, b int) int { if a < b { return a } return b }
-
function mincostTickets(days: number[], costs: number[]): number { const n = days.length, m = days[n - 1] + 1; const [a, b, c] = costs; let dp = new Array(m).fill(0); for (let i = 1; i < m; i++) { let x = days.includes(i) ? dp[i - 1] + a : dp[i - 1]; let y = (i > 7 ? dp[i - 7] : dp[0]) + b; let z = (i > 30 ? dp[i - 30] : dp[0]) + c; dp[i] = Math.min(x, y, z); } return dp[m - 1]; }