minimum-cost-for-tickets.cpp

// Time:  O(n)
// space: O(1)

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        static vector<int> durations{1, 7, 30};
        
        const int W = durations.back();
        vector<int> dp(W, numeric_limits<int>::max());
        dp[0] = 0;
        vector<int> last_buy_days{0, 0, 0};
        for (int i = 1; i < days.size() + 1; ++i) {
            dp[i % W] = numeric_limits<int>::max();
            for (int j = 0; j < durations.size(); ++j) {
                while (i - 1 < days.size() &&
                       days[i - 1] > days[last_buy_days[j]] + durations[j] - 1) {
                    ++last_buy_days[j];  // Time: O(n)
                }
                dp[i % W] = min(dp[i % W], dp[last_buy_days[j] % W] + costs[j]);
            }
        }
        return dp[days.size() % W];
    }
};