简介
题解
方法一
我们使用 \(dp(i)\) 表示从第 \(i\) 天到第365天需要花费的钱，于是存在两种情况：
- 第 \(i\) 天并不是需要出行的日子，这时我们可以贪心地选择不买，即 \(dp(i) = dp(i+1)\) ，这是因为通行证越晚买越好。
- 第 \(i\) 天是需要出行的日子，我们可以选择买 1，7 或 30 天的通行证。若我们购买了 \(j\) 天的通行证，那么接下来的 \(j−1\) 天，我们都不再需要购买通行证，只需要考虑第 \(i+j\) 天及以后即可。因此，我们有: $$dp(i)=min(min(dp(i + 1) + costs[0], dp(i + 7) + costs[1]), dp(i + 30) + costs[2])$$
如果我们需要购买通行证，那么一定越晚买越好，在握着一张有效的通行证的时候购买其它的通行证显然是不划算的,因此只需要考虑第 \(i + j\) 天即以后。
采取记忆化搜索，防止重复计算，最终答案为dp(1)，代码如下：
class Solution {
public:
unordered_set<int> dayset;
vector<int> costs;
int memo[366]{0};
int mincostTickets(vector<int>& days, vector<int>& costs) {
this -> costs = costs;
for(auto d : days)
dayset.insert(d);
memset(memo, -1, sizeof(memo));
return dp(1);
}
int dp(int i)
{
if(i > 365)
return 0;
if(memo[i] != -1)
return memo[i];
if(dayset.count(i))
{
memo[i] = min(min(dp(i + 1) + costs[0], dp(i + 7) + costs[1]), dp(i + 30) + costs[2]);
}
else
{
memo[i] = dp(i + 1);
}
return memo[i];
}
};
这里有一个小技巧，将dayset,costs设置为类私有变量，然后在mincostTickets里进行赋值，可以直接在dp函数中访问到。如果将这二者设置在mincostTickets中，dp需要设置多个形参来接受它们，才能访问到二者。
时间复杂度为 \(O(W)\)，\(W\) 是最大的日期数。
方法二
方法一需要遍历一年中所有的天数，无论 \(days\) 的长度是多少。
但是观察方法一的递推式，我们可以看到，如果我们查询 \(dp(i)\) ，而第 \(i\) 天我们又不需要出行的话，那么 \(dp\) 函数会一直向后计算 \(dp(i+1)=dp(i+2)=dp(i+3)=...\) 一直到一年结束或者有一天我们需要出行为止。那么我们其实可以直接跳过这些不需要出行的日期，直接找到下一个需要出行的日期。
代码如下：
class Solution {
private:
vector<int> days, costs;
vector<int> memo;
int durations[3] = {1, 7, 30};
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
this->days = days;
this->costs = costs;
memo.assign(days.size(), -1);
return dp(0);
}
int dp(int i) {
if (i >= days.size()) {
return 0;
}
if (memo[i] != -1) {
return memo[i];
}
memo[i] = INT_MAX;
int j = i;
for (int k = 0; k < 3; ++k) {
while (j < days.size() && days[j] < days[i] + durations[k]) {
++j;
}
memo[i] = min(memo[i], dp(j) + costs[k]);
}
return memo[i];
}
};
其实所有的动态规划问题都有一个思想，它不去考虑具体的问题处理方法，而是把一系列事件看作一个状态，比如这个问题，将 \(dp(i)\) 视作从第 \(days[i]\) 天开始至旅行结束的开销，而不去具体地考虑每一天或每几天的处理方式，而将处理方式的细节掩藏进状态转移方程里。