Memoizing a backtracking problem with multiple variables

Question

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!

Answer 1

You can return the cheapest costs for given index. This can be cached easily. Like that you can also get rid of the window and the costs so far. Otherwise it is still your solution:

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

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

private int backtrack(int[] days, int[] costs, int index, ​int[] memory) {
    ​if (memory[index] > 0) return memory[index];
    ​int cost = Integer.MAX_VALUE;
    ​for (int j = 0; j < costs.length; j++) {
        ​int currCost = costs[j];
        int next = index + 1;
        while (next < days.length && days[next] - days[index] < durations[j])
            next++;
        if (next < days.length)
            currCost += backtrack(days, costs, next, memory);
        ​cost = Math.min(cost, currCost);
   ​ }​
    memory[index] = cost;
   ​ return cost;
}

I don't see any other good solution. Because costs so far will change for the same index and therefore using exactly your way is not working. I also don't think this is a dp solution, because that would build on what we already have. So we would have to start at the last day and go backwards. Well in the end it is almost the same.

This would be the dynamic programming solution. It doesn't need recursion. This would be my preferred solution, in my opinion the one proposed by Poby in your link is pretty bad (not performance, but elegance, simplicity and programming style, not even doing the 1, 7, 30 days in a loop like you did):

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

public int mincostTickets(int[] days, int[] costs) {
    if (days.length == 0) return 0;
    int[] dp = new int[days.length];
    for (int i = days.length - 1; i >= 0; i--) {
        int best = Integer.MAX_VALUE;
        for (int j = 0; j < costs.length; j++) {
            int cost = costs[j];
            int next = i + 1;
            while (next < days.length && days[next] - days[i] < durations[j])
                next++;
            if (next < days.length)
                cost += dp[next];
            best = Math.min(cost, best);
        }
        dp[i] = best;
    }
    return dp[0];
}

Time complexity is O(n) for both solutions. If we would say costs and durations are dynamic, so m is the number of different tickets you can buy, then you could find the next day using bisection. This would give O(nmlogn) for the generalized solution.