I'm trying to solve this problem, and I am able to solve it using backtracking. However I am not able to think of the right way to memoize it, given that there are multiple variables (index of days array keeps changing and for each day we try out different costs), and hence needed some help. Here is my code which seems to be working fine, but it clearly is doing repeat computations

private int[] durations = {1, 7, 30};

public int mincostTickets(int[] days, int[] costs) {
    if (days.length == 0) return 0;
    return backtrack(days, costs, 0, 0, 0);
}

private int backtrack(int[] days, int[] costs, int index, int costSoFar, int window) {
    
    if (index >= days.length ) {
        return costSoFar;
    }
    
    int cost = Integer.MAX_VALUE;
    for (int j = 0; j < costs.length; j  ) {
        int currCost = 0;
        if (days[index] >= window ) {
            currCost = backtrack(days, costs, index   1, costSoFar   costs[j], days[index]   durations[j]);
        } else {
            currCost = backtrack(days, costs, index   1, costSoFar, window);
        }
        cost = Math.min(cost, currCost);
    }

    return cost;
}

Also if you can help me understand the time complexity here, that'd be great!

CodePudding user response：

so far as you wrote the codes, complexity is like O(N).

CodePudding user response：

You could memoize your solution in a way like this:

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int[] dp = new int[days.length];
        Arrays.fill(dp, -1);
        return rec(days, costs, 0, dp);
    }

    int rec(int[] days, int[] costs, int idx, int[] dp) {
        if (idx >= days.length)
            return 0;
        if (dp[idx] != -1)
            return dp[idx];
        // 1 day pass
        int min = Integer.MAX_VALUE;
        min = Math.min(min, costs[0]   rec(days, costs, idx   1, dp));
        // 7 day pass
        int tarDay = days[idx]   costs[1];
        int i = idx;
        while (i < days.length && days[i] < tarDay) i  ;
        min = Math.min(min, costs[1]   rec(days, costs, i, dp));
        // 30 day pass
        tarDay = days[idx]   costs[2];
        while (i < days.length && days[i] < tarDay) i  ;
        min = Math.min(min, costs[2]   rec(days, costs, i, dp));
        return dp[idx] = min;
    }
}

After recursion the complexity of your code would be O(n) because of multiple saved states and pre-computations. Otherwise since you'll be accessing all the states, it'll be n^2.