[LeetCode] 983. Minimum Cost For Tickets

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.

最低票价。影子题322。

题意是给你一个未来365天的出行计划，用数组表示哪一天需要出行；同时给你一个火车的价目表，请你计算如何订票花费最少。其中，火车票票价的表达是这样的，

a 1-day pass is sold for costs[0] dollars; - 一天票costs[0]用表示
a 7-day pass is sold for costs[1] dollars; - 7天票用costs[1]表示
a 30-day pass is sold for costs[2] dollars. - 30天票用costs[2]表示

思路是DP动态规划。首先用一个长度为366的boolean数组记录哪些天需要出行，为什么是366是因为日期是从1开始的，不是从0；然后创建一个DP数组，长度也为366，数组的意义是如果某一天要出行，所有需要的最小花费是多少。有如下几种情况需要考虑

首先第0天的花费自然是0

如果某一天不需要出行，他的花费理应跟他前一天一样

如果某一天需要出行，需要在如下几种情况找他的最大花费

一天前的花费 + 一天的车票钱
七天前的花费 + 七天的车票钱
三十天前的花费 + 三十天的车票钱

所以代码就呼之欲出了。

时间O(1) - 最多检查366次

空间O(n) - 两个长度为366的数组

Java实现

 1 class Solution {
 2     public int mincostTickets(int[] days, int[] costs) {
 3         boolean[] isTravelDay = new boolean[366];
 4         for (int day : days) {
 5             isTravelDay[day] = true;
 6         }
 7         int[] dp = new int[366];
 8         for (int i = 1; i < 366; i++) {
 9             if (!isTravelDay[i]) {
10                 dp[i] = dp[i - 1];
11                 continue;
12             }
13             dp[i] = Integer.MAX_VALUE;
14             dp[i] = Math.min(dp[i], dp[Math.max(0, i - 1)] + costs[0]);
15             dp[i] = Math.min(dp[i], dp[Math.max(0, i - 7)] + costs[1]);
16             dp[i] = Math.min(dp[i], dp[Math.max(0, i - 30)] + costs[2]);
17         }
18         return dp[365];
19     }
20 }