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 1day pass is sold for
costs[0]
dollars;  a 7day pass is sold for
costs[1]
dollars;  a 30day pass is sold for
costs[2]
dollars.
The passes allow that many days of consecutive travel. For example, if we get a 7day 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 1day pass for costs[0] = $2, which covered day 1. On day 3, you bought a 7day pass for costs[1] = $7, which covered days 3, 4, ..., 9. On day 20, you bought a 1day 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 30day pass for costs[2] = $15 which covered days 1, 2, ..., 30. On day 31, you bought a 1day 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 Topdown
// OJ: https://leetcode.com/problems/minimumcostfortickets/
// 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 Bottomup
// OJ: https://leetcode.com/problems/minimumcostfortickets/
// 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];
}
};
Java

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; } }

// OJ: https://leetcode.com/problems/minimumcostfortickets/ // 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(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]]