/*
Runtime: 1 ms, faster than 92.91% of Java online submissions for Minimum Cost For Tickets.
Memory Usage: 34.7 MB, less than 100.00% of Java online submissions for Minimum Cost For Tickets.
*/

class Solution {
    int[] cache;
    int[] days;
    int[][] costs = new int[3][2];
    public int mincostTickets(int[] days, int[] costs) {
        if (days.length == 0) return 0;
        this.days=days;
        this.costs[0][0] = 1;
        this.costs[1][0] = 7;
        this.costs[2][0] = 30;
        this.costs[0][1] = costs[0];
        this.costs[1][1] = costs[1];
        this.costs[2][1] = costs[2];
        this.cache = new int[days.length];
        return minCostTickets(days.length-1);
    }

    private int minCostTickets(int dayP) {
        if (cache[dayP] != 0) return cache[dayP];

        int cost = -1;
        int day = days[dayP];
        for(int[] ticket : costs) {
            int prevDay = day - ticket[0];
            int dayId = Arrays.binarySearch(days, prevDay);
            int currentCost;
            if (dayId == -1) { // before 1stDay
                currentCost = ticket[1];
            } else {
                if (dayId < 0) {
                    dayId = -dayId - 1 - 1;
                }
                currentCost = ticket[1] + minCostTickets(dayId);
            }

            cost = cost == -1 ? currentCost : Math.min(cost, currentCost);
        }
        cache[dayP] = cost;
        return cost;
    }
}