[LeetCode] 983. Minimum Cost For Tickets

[grandyang]

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.

Note:

1. 1 <= days.length <= 365
2. 1 <= days[i] <= 365
3. days is in strictly increasing order.
4. costs.length == 3
5. 1 <= costs[i] <= 1000

这道题给了两个数组 days 和 costs，说是有人会在指定的天数进行旅游，由于某些城市的旅游景点比较多，短时间内可能玩不完，所有有些城市会推出 city pass，就是在特定的天数内，可以随意玩。这里博主不得不提亚特兰大的 city pass，总体感觉还是蛮划算的，可以玩的很开心。现在说是有三种 city pass，一天，一周，和一个月的通玩票，价格不同，现在问应该如何去买，才能保证在给定的天数都玩到，而且花费最小。当然实际情况中，肯定是月票价格大于周票大于日票，但是这道题里并没有这个限制，cost 值之间并不存在大小关系。在实际情况中，如果需要连着几天玩，肯定是用长期票划算，但这里不一定哦，所以一定要算出各种情况。像这种每天游玩的票可以有三种不同的选择，即三种不同的状态，又是一道求极值的问题，可以说基本上动态规划 Dynamic Programming 就是不二之选。这里可以使用一个一维的 dp 数组，其中 dp[i] 表示游玩到第 days[i] 天时所需要的最小花费。接下来就是最难的部分了，找出状态转移方程。对于第 days[i] 天的花费，可能有三种不同的情况，首先是第 days[i-1] 使用了一张日票，则当前天就有多种选择，可以买日票，周票，或者月票。若之前使用买过了周票，则当前并不用再花钱了，所以只要一周内买过周票，当前就不用花钱了，但是当前的 dp 值还是需要被更新的，用买周票的前一天的 dp 值加上周票的价格来更新当前的 dp 值，所以显而易见是需要两个 for 循环的，外层的是遍历游玩天数，内层是不停的通过用买周票或者月票的方式，来查找一种最省钱的方法。具体来看代码，这里的 dp 数组大小为 n+1，为了防止减1溢出，并且都初始化为整型最大值，但是 dp[0] 要初始化为0。然后就是外层 for 循环了，i从1遍历到n，由于每一天都可以买日票，所以都可以用前一天的 dp 值加上日票价格来更新当前的 dp 值。然后就是内层循环了，j从1遍历到i，只要遍历到的某天在当前天的7天之内，就可以用尝试着替换成周票来更新当前的 dp 值，同理，若只要遍历到的某天在当前天的 30 天之内，就可以用尝试着替换成月票来更新当前的 dp 值，这样更新下来，最优解就会存到 dp 数组种的最后一个位置上了，参见代码如下：

解法一：

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 = 1; i <= n; ++i) {
            dp[i] = min(dp[i], dp[i - 1] + costs[0]);
            for (int j = 1; j <= i; ++j) {
                if (days[j - 1] + 7 > days[i - 1]) {
                    dp[i] = min(dp[i], dp[j - 1] + costs[1]);
                }
                if (days[j - 1] + 30 > days[i - 1]) {
                    dp[i] = min(dp[i], dp[j - 1] + costs[2]);
                }
            }
        }
        return dp.back();
    }
};

下面来看一种更简洁的写法，由于规定了游玩的天数是在一年内，实际上可以将 dp 数组的大小确定为 366，然后只要更新好这个 dp 数组就行了。同时，由于并不是每天都要玩，所以需要知道到底是哪些天需要玩，比较简单的方法就是把游玩的天数放到一个 TreeSet 中，以便于快速的查询。用 for 循环遍历1到 365 天，用前一天的 dp 值来更新当前天，因为就算今天没有玩，之前花了的钱也都已经花了，还是要记在那，以便年底算总账。若当前天游玩了，即在 TreeSet 里面，则考虑是否可以优化当前的花费，通过三种途径，今天买日票，一周前买周票，或者一个月钱买月票，看哪种花费最低，用来更新当前的 dp 值，参见代码如下：

解法二：

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        unordered_set<int> st(days.begin(), days.end());
        vector<int> dp(366);
        for (int i = 1; i <= 365; ++i) {
            dp[i] = dp[i - 1];
            if (st.count(i)) {
                dp[i] = min({dp[i - 1] + costs[0], dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2]});
            }
        }
        return dp.back();
    }
};

Github 同步地址:

#983

类似题目：

Coin Change

参考资料：

https://leetcode.com/problems/minimum-cost-for-tickets/

https://leetcode.com/problems/minimum-cost-for-tickets/discuss/226659/Two-DP-solutions-with-pictures

https://leetcode.com/problems/minimum-cost-for-tickets/discuss/630868/explanation-from-someone-who-took-2-hours-to-solve

LeetCode All in One 题目讲解汇总(持续更新中...)

[PicassosHair]

非常感谢你的分享。这种方法有一个隐含的前提：月票比周票贵，周票比日票贵。如果输入为：

days: [1,4,6,7,8,20]
costs: [7,2,15]

本方法输出结果为11，但实际上只需要6的cost。

[lld2006]

方法1 是O（N ^2), 方法2， 每天都要dp， 优点麻烦。
我用了一下lower_bound, 好像速度还不错。

class Solution {
public:
    int mincostTickets(vector& days, vector& costs) {
      days.push_back(days.back()+31);
      vector< int> dp(days.size(), numeric_limits< int>::max());    
      dp[0] = 0;
      vector pass ={1,7,30};
      for(int i =0; i< days.size()-1; ++i){
        for(int j = 0; j < pass.size(); ++j) {
          int target = days[i] + pass[j];
          auto iter = lower_bound(days.begin(), days.end(), target);
          int idx = distance(days.begin(), iter);
          dp[idx] = min(dp[idx], dp[i]+costs[j]);
        }   
      }
      return dp.back();
    }
};

[grandyang]

方法1 是O（N ^2), 方法2， 每天都要dp， 优点麻烦。
我用了一下lower_bound, 好像速度还不错。

class Solution {
public:
int mincostTickets(vector& days, vector& costs) {
days.push_back(days.back()+31);
vector< int> dp(days.size(), numeric_limits< int>::max());
dp[0] = 0;
vector pass ={1,7,30};
for(int i =0; i< days.size()-1; ++i){
for(int j = 0; j < pass.size(); ++j) {
int target = days[i] + pass[j];
auto iter = lower_bound(days.begin(), days.end(), target);
int idx = distance(days.begin(), iter);
dp[idx] = min(dp[idx], dp[i]+costs[j]);
}
}
return dp.back();
}
};

赞一个～

[grandyang]

非常感谢你的分享。这种方法有一个隐含的前提：月票比周票贵，周票比日票贵。如果输入为：

days: [1,4,6,7,8,20]
costs: [7,2,15]

本方法输出结果为11，但实际上只需要6的cost。

是都返回6啊