983. Minimum Cost For Tickets

dp + memo
O(n) time O(n) space

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        n = days.size();
        cost.resize(n);
        vector<int> passes = {1, 7, 30};
        return mincost(0, days, 0, passes, costs); // lastDay从0开始，因为不知道days都是哪些天
    }

    int mincost(int lastDay, const vector<int> &days, int nextIdx, const vector<int> &passes, const vector<int> &costs) {
        if (nextIdx >= n) return 0;
        if (days[nextIdx] <= lastDay) return mincost(lastDay, days, nextIdx + 1, passes, costs); // 如果之前买的票可以cover当前这一天days[nextIdx]则继续测试days[nextIdx + 1]
        if (cost[nextIdx] > 0) return cost[nextIdx];
        int res = INT_MAX;
        for (int i = 0; i < 3; ++i) {
            res = min(res, mincost(days[nextIdx] + passes[i] - 1, days, nextIdx + 1, passes, costs) + costs[i]); // 分别测试三种票哪种可以使得总票价最低
        }
        return cost[nextIdx] = res;
    }

    int n;
    vector<int> cost; // cache
};