package leetcode;

/**
 * https://leetcode.com/problems/minimum-cost-for-tickets/
 */
public class Problem983 {
    public int mincostTickets(int[] days, int[] costs) {
        return minCostTickets(days, costs, 0);
    }

    private static int minCostTickets(int[] days, int[] costs, int index) {
        if (index == days.length) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < costs.length; i++) {
            int nDays = 0;
            if (i == 0) {
                nDays = 1;
            } else if (i == 1) {
                nDays = 7;
            } else {
                nDays = 30;
            }
            int toDay = days[index] + nDays;
            int j = index + 1;
            for (; j < days.length; j++) {
                if (days[j] >= toDay) {
                    break;
                }
            }
            int c = minCostTickets(days, costs, j) + costs[i];
            min = Math.min(min, c);
        }
        return min;
    }

    public static void main(String[] args) {
        Problem983 prob = new Problem983();
        System.out.println(prob.mincostTickets(new int[]{1, 4, 6, 7, 8, 20}, new int[]{2, 7, 15})); // 11
        System.out.println(prob.mincostTickets(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31}, new int[]{2, 7, 15})); // 17
    }
}

@@ -158,24 +158,75 @@
 %5B%5D costs) %7B%0A
+        Integer%5B%5D memo = new Integer%5Bdays.length%5D;%0A
         retu
@@ -257,16 +257,22 @@
 costs, 0
+, memo
 );%0A    %7D
@@ -345,16 +345,32 @@
 nt index
+, Integer%5B%5D memo
 ) %7B%0A    
@@ -425,32 +425,109 @@
 rn 0;%0A        %7D%0A
+        if (memo%5Bindex%5D != null) %7B%0A            return memo%5Bindex%5D;%0A        %7D%0A
         int min 
@@ -1066,16 +1066,22 @@
 costs, j
+, memo
 ) + cost
@@ -1144,347 +1144,46 @@
     
-return min;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem983 prob = new Problem983();%0A        System.out.println(prob.mincostTickets(new int%5B%5D%7B1, 4, 6, 7, 8, 20%7D, new int%5B%5D%7B2, 7, 15%7D)); // 11%0A        System.out.println(prob.mincostTickets(new int%5B%5D%7B1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31%7D, new int%5B%5D%7B2, 7, 15%7D)); // 17
+memo%5Bindex%5D = min;%0A        return min;
 %0A   

Solve problem 983