leetcode Daily Challenge on August 25th, 2020.
Difficulty : Medium
Related Topics : Dynamic Programming
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 from1
to365
.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.
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.
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.
1 <= days.length <= 365
1 <= days[i] <= 365
days
is in strictly increasing order.costs.length == 3
1 <= costs[i] <= 1000
- mine
- Java
Runtime: 1 ms, faster than 89.33%, Memory Usage: 39.1 MB, less than 42.02% of Java online submissions
// O(W)time // O(W)space // W = Max(day) + 31 public int mincostTickets(int[] days, int[] costs) { //dp[i] = dp[i- 1] + cost[0] dp[i-7]+cost[1] dp[i-30] + cost[2] int n = days.length; int max = days[n - 1] + 31; int[] dp = new int[max]; int before = 0; for (int day : days) { int index = day + 30; getMinCost(dp, costs, before, index); before = index; } return dp[max - 1]; } void getMinCost(int[] dp, int[] costs, int before, int index) { for (int i = before + 1; i < index; i++) { dp[i] = dp[before]; } dp[index] = dp[index - 1] + costs[0]; dp[index] = Math.min(dp[index], dp[index - 7] + costs[1]); dp[index] = Math.min(dp[index], dp[index - 30] + costs[2]); }
- Java
- the most votes
- Dynamic Programming (Window Variant)
Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.9 MB, less than 97.51% of Java online submissions
// O(N)time // O(N)space // N is days.length int[] days, costs; Integer[] memo; int[] durations = new int[]{1, 7, 30}; public int mincostTickets(int[] days, int[] costs) { this.days = days; this.costs = costs; memo = new Integer[days.length]; return dp(0); } public int dp(int i) { if (i >= days.length) return 0; if (memo[i] != null) return memo[i]; int ans = Integer.MAX_VALUE; int j = i; for (int k = 0; k < 3; ++k) { while (j < days.length && days[j] < days[i] + durations[k]) j++; ans = Math.min(ans, dp(j) + costs[k]); } memo[i] = ans; return ans; }