[[DP]]
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式 ：
- 一张 为期一天 的通行证售价为
costs[0]美元； - 一张 为期七天 的通行证售价为
costs[1]美元； - 一张 为期三十天 的通行证售价为
costs[2]美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。
记忆化搜索版本
```cpp
class Solution {
public:
int ticket[3] = {1,7,30};
int dp[366];
int n;
int f(vector<int>& days, vector<int>& costs, int i) {
if(i >= n) {
return 0;
}
if(dp[i] != inf) {
return dp[i];
}
for(int j = i, k = 0; k < 3; k++) {
dbg(i,k);
while(j < n && days[j] - days[i] < ticket[k]) {
j++;
}
dp[i] = min(dp[i],costs[k] + f(days, costs, j));
}
return dp[i];
}
int mincostTickets(vector<int>& days, vector<int>& costs) {
memset(dp,0,sizeof(dp));
n = days.size();
_rep(i,0,n) dp[i] = inf;
f(days,costs,0);
return dp[0];
}
};
dp[i] 表示从第i个位置开始到终点花费的金额
DP
自底到顶，n位置的成本为0，从n-1到0，每次都能确定一个最小值，可以被下次访问时直接取得，无需继续遍历,且dp直接取得的值和记忆化搜索从记忆表中取得的值是一个东西
class Solution {
public:
int ticket[3] = { 1,7,30 };
int dp[366];
int n;
int mincostTickets(vector<int>& days, vector<int>& costs) {
memset(dp, 0, sizeof(dp));
n = days.size();
dp[n] = 0;
_rep(i, 0, n - 1) dp[i] = inf;
rep_(i, n - 1, 0) {
for (int j = i, k = 0; k < 3; k++) {
while (j < n && days[j] - days[i] < ticket[k]) {
j++;
}
dp[i] = min(dp[i],costs[k] + dp[j]);
}
}
return dp[0];
}
};