记忆具有多个变量的回溯问题

Question

我正在尝试解决 this problem，并且我能够使用回溯解决它。但是我想不出正确的方法来记住它，因为有多个变量（天数数组的索引不断变化，每天我们尝试不同的成本），因此需要一些帮助。这是我的代码，它似乎工作正常，但它显然正在进行重复计算

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;
}

另外，如果你能帮助我理解这里的时间复杂度，那就太好了！

Answer 1

您可以通过以下方式记住您的解决方案：

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;
    }
}

递归后代码的复杂性将是 O(n)，因为有多个保存的状态和预计算。否则，由于您将访问所有州，因此它将是 n^2.

Answer 2

您可以 return 给定索引的最低费用。这可以很容易地缓存。这样你也可以摆脱 window 和到目前为止的成本。否则它仍然是你的解决方案：

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;
}

我没有看到任何其他好的解决方案。因为到目前为止，同一索引的成本会发生变化，因此完全使用您的方式是行不通的。我也不认为这是 dp 解决方案，因为那将建立在我们已有的基础上。所以我们必须从最后一天开始，然后倒退。嗯，最后差不多了。

这将是动态规划解决方案。它不需要递归。这将是我的首选解决方案，在我看来，Poby 在您的 link 中提出的解决方案非常糟糕（不是性能，而是优雅、简单和编程风格，甚至没有在循环中执行 1、7、30 天就像你一样）：

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];
}

两种解决方案的时间复杂度均为 O(n)。如果我们说成本和持续时间是动态的，那么 m 是您可以购买的不同门票的数量，那么您可以使用二分法找到第二天。这将为广义解决方案提供 O(nmlogn)。

记忆具有多个变量的回溯问题

Memoizing a backtracking problem with multiple variables

java

algorithm

memoization