思路

日期变量型思路需要遍历一年中所有的天数，无论 days 的长度是多少。

但是观察日期变量型的递推式，我们可以看到，如果我们查询 dp(i)，而第 i 天我们又不需要出行的话，那么 dp 函数会一直向后计算 dp(i+1)=dp(i+2)=dp(i+3) 一直到一年结束或者有一天我们需要出行为止。那么我们其实可以直接跳过这些不需要出行的日期，直接找到下一个需要出行的日期。

算法

现在，我们令 dp(i) 表示能够完成从第 days[i] 天到最后的旅行计划的最小花费（注意，不再是第 i 天到最后的最小花费）。令 j1是满足 days[j1]>=days[i]+1 的最小下标，j7是满足 days[j7]>=days[i]+7 的最小下标， j30是满足 days[j30]>=days[i]+30 的最小下标，那么就有：
dp(i)=min(dp(j 1 )+costs[0],dp(j 7 )+costs[1],dp(j 30 )+costs[2])

#include <bits/stdc++.h>
using namespace std;

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;
  ...