原题链接在这里:
题目:
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 <= 365
1 <= days[i] <= 365
days
is in strictly increasing order.costs.length == 3
1 <= costs[i] <= 1000
题解:
For all the days when travel is not needed, its min cost should be the same as previous day.
When it comes to the day travel is needed, there are 3 options, 1 day pass + up to previous day minimum cost, 7 days pass + up to previous 7 days minimum cost, 30 days pass + up to previous 30 days minimum cost.
Time Complexity: O(n). n = days[days.length-1].
Space: O(n).
AC Java:
1 class Solution { 2 public int mincostTickets(int[] days, int[] costs) { 3 int lastDay = days[days.length-1]; 4 int [] dp = new int[lastDay+1]; 5 int ind = 0; 6 for(int i = days[0]; i<=lastDay; i++){ 7 if(i != days[ind]){ 8 dp[i] = dp[i-1]; 9 }else{10 dp[i] = Math.min(dp[i-1]+costs[0], Math.min(dp[Math.max(0, i-7)]+costs[1], dp[Math.max(0, i-30)]+costs[2]));11 ind++;12 }13 }14 15 return dp[lastDay];16 }17 }
The truth is we only need to maintain last 30s data.
Thus it couls limit dp array to 30 days.
Time Complexity: O(n).
Space: O(1).
AC Java:
1 class Solution { 2 public int mincostTickets(int[] days, int[] costs) { 3 int [] dp = new int[30]; 4 int ind = 0; 5 for(int i = days[0]; i<=days[days.length-1]; i++){ 6 if(i != days[ind]){ 7 dp[i%30] = dp[(i-1)%30]; 8 }else{ 9 dp[i%30] = Math.min(dp[(i-1)%30] + costs[0], Math.min(dp[Math.max(0, i-7) % 30] + costs[1], dp[Math.max(0, i-30) % 30] + costs[2]));10 ind++;11 }12 }13 14 return dp[days[days.length-1]%30];15 }16 }
类似.