多变量回溯问题的记忆化优化咨询（以LeetCode983最低票价为例）

记忆化优化实现 #

你原有回溯的核心问题是状态参数设计不合理：costSoFar属于累计过程值，不需要纳入缓存状态，我们可以将回溯返回值定义为从第index个出行日开始，当前购票有效期覆盖到window天，后续需要花费的最小成本，仅需缓存(index, window)两个变量的对应结果即可消除重复计算。
另外因为题目给定的days数组为严格递增序列，我们还可以提前剪枝：当有效期window >= 当前出行日days[index]时，无需重复遍历三种购票方案，直接跳到下一个出行日即可，消除冗余分支。
优化后的带记忆化的代码如下：

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

public int mincostTickets(int[] days, int[] costs) {
    int n = days.length;
    if (n == 0) return 0;
    // 有效期最大不会超过最后一天+30，第二维开400足够覆盖所有场景
    memo = new Integer[n][400];
    return backtrack(days, costs, 0, 0);
}

private int backtrack(int[] days, int[] costs, int index, int window) {
    if (index >= days.length) {
        return 0;
    }
    if (memo[index][window] != null) {
        return memo[index][window];
    }
    
    int res = 0;
    if (days[index] < window) {
        // 当前天仍在有效期内，直接处理下一天
        res = backtrack(days, costs, index + 1, window);
    } else {
        // 需要买新票，遍历三种方案取最小
        res = Integer.MAX_VALUE;
        for (int j = 0; j < costs.length; j++) {
            int newWindow = days[index] + durations[j];
            // 避免数组越界，超过395的统一存为399不影响计算结果
            if (newWindow >= 400) newWindow = 399;
            int currCost = costs[j] + backtrack(days, costs, index + 1, newWindow);
            res = Math.min(res, currCost);
        }
    }
    memo[index][window] = res;
    return res;
}

如果要进一步提升性能，可以在购买新票后用二分查找直接定位到第一个超过有效期的出行日下标，跳过中间不需要处理的日期，减少递归次数。

时间复杂度分析 #

• 原始回溯版本：每个出行日对应3种分支选择，且无缓存会重复计算，最坏时间复杂度为O(3^n)，其中n为days数组的长度，n较大时会严重超时。
• 记忆化优化版本：总状态数为n * 400，每个状态仅计算一次，时间复杂度为O(n)，可以轻松通过所有测试用例。如果增加二分跳转优化，时间复杂度仍为O(n)，实际运行速度会更快。

内容的提问来源于stack exchange，提问作者Ufder