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: 11Explanation: 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: 17Explanation: 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 <= 3651 <= days[i] <= 365days is in strictly increasing order.costs.length == 31 <= costs[i] <= 1000
难度：medium
题目：某国流行火车旅行，可以提前一年制订火车旅行计划。要出行的日子以数组的形式给出。出行的日子为 1 到 365 之间的整数。
火车票以 3 种形式出售：1 天通行票 7 天通行票 30 天通行票通行票允许多天持续旅行。例如，如果在第 2 天购得 7 天通行票，那么在接下来的 7 天，第 3 天，4 天，5 天，6 天，7 天，8 天持续旅行。
返回所有旅行天数所用的最小的旅行花费。
思路：动态规划问题可以拆解，设当天为 n, 则 daysCost(n) = costs(n) + Math.min(daysCost(n – 1), daysCost(n – 7), daysCost(n – 30)) (n 为计划旅行日)daysCost(n) = daysCost(n – 1) (n 为非计划旅行日）
Runtime: 4 ms, faster than 100.00% of Java online submissions for Minimum Cost For Tickets.
class Solution {
public int mincostTickets(int[] days, int[] costs) {
int n = days.length;
int[] dcs = new int [366];
for (int i = 0; i < n; i++) {
dcs[days[i]] = 1;
}
for (int i = 1; i < 366; i++) {
if (0 == dcs[i]) {
dcs[i] = dcs[i – 1];
} else {
dcs[i] = Math.min(costs[0] + dcs[i – 1],
Math.min(costs[1] + dcs[Math.max(0, i – 7)],
costs[2] + dcs[Math.max(0, i – 30)]));
}
}
return dcs[days[n – 1]];
}
}