// Runtime: 1 ms, faster than 92.91% of Java online submissions for Minimum Cost For Tickets.
// Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Minimum Cost For Tickets.
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int ix = 0;

        int[] len = { 1, 7, 30 };
        int[] dp = new int[366];

        dp[0] = 0;

        for (int i = 1; i <= 365 && ix < days.length; i++) {
            if (i != days[ix]) {
                dp[i] = dp[i - 1];
                continue;
            }

            ix++;

            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < 3; j++) {
                if (ix == 0) {
                    dp[i] = Math.min(dp[i], costs[j]);
                }
                else {
                    int back = Math.max(0, i - len[j]);
                    dp[i] = Math.min(dp[i], dp[back] + costs[j]);
                }
            }
        }

        return dp[days[ix-1]];
    }
}