LeetCode 1575. 统计所有可行路径

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 微软
标签
数组 动态规划 记忆化

题目描述

✅ 1575. 统计所有可行路径

image-20260929085317985

image-20260929085318102

题意分析

从 start 城市出发，每次可以移动到任意其他城市，消耗两地坐标差的绝对值。油量不能变成负数，允许重复经过城市，要求统计最终停在 finish 的所有路线，并对 10^9 + 7 取模。

到过终点不代表路线必须结束：可以当场停止，也可以继续离开并在油量允许时返回。不同的城市访问序列分别计数，不要求恰好用完全部燃油。

解法：记忆化搜索

核心思路

[!blue]

在本次城市坐标与终点固定的前提下，定义 dfs(pos, fuel) 为从当前城市 pos、剩余 fuel 单位燃油开始，最终停在终点的路线数。可选后续只由这两个量决定，之前走过哪些城市不影响后续选择，因此可以按它们记忆化。

若 pos == finish，先计入“现在停止”这一条路线，初值为 1；否则初值为 0。然后枚举所有其他城市 next，只要移动代价 cost 不超过剩余燃油，就累加 dfs(next, fuel - cost)。这些路线按下一站分组，相互不重叠，再加上不移动的停止选择，覆盖了当前状态的全部可能。

城市坐标互不相同，且禁止移动到自己，所以每次转移都消耗正燃油。即使以后回到同一城市，剩余燃油也更少，不会形成状态递归环；油量为零时无需特殊分支，已没有合法移动，只有位于终点时贡献 1。

用 -1 表示状态尚未计算，因为 0 也可能是合法答案。相同状态复用的是后续方案数量，不会把不同前缀的路线合并成一条；每个调用来源仍会把这个数量加入自己的计数。每次累加及时取模，再保存结果。

解题步骤

  1. 每次公开调用创建新的二维缓存，大小为城市数乘以 初始燃油 + 1，全部初始化为 -1。
  2. 从 dfs(start, fuel) 开始；若状态已有缓存，直接返回。
  3. 当前城市是终点时将局部答案设为 1，否则设为 0。
  4. 枚举不同于当前城市的目的地，计算距离；燃油足够时累加对应剩余状态的答案并取模。
  5. 缓存当前计数并返回，直到获得初始状态的答案。

代码实现

class Solution {
    private static final int MOD = 1_000_000_007;
    private int[] loc;
    private int finish;
    private int[][] memo;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        this.loc = locations;
        this.finish = finish;
        int n = locations.length;

        memo = new int[n][fuel + 1];

        for (int i = 0; i < n; i++) {
            for (int f = 0; f <= fuel; f++) {
                memo[i][f] = -1;
            }
        }

        return dfs(start, fuel);
    }

    private int dfs(int pos, int fuel) {
        if (memo[pos][fuel] != -1) {
            return memo[pos][fuel];
        }

        long answer = 0;

        // 终点先计入现在停止的路线，仍继续搜索离开后返回的路线。
        if (pos == finish) {
            answer = 1;
        }

        for (int next = 0; next < loc.length; next++) {
            // 禁止零消耗原地移动，其他城市坐标不同，油量严格下降。
            if (next == pos) {
                continue;
            }

            int cost = Math.abs(loc[pos] - loc[next]);

            // 油量恰好够用也能移动，同一城市可在不同剩余油量下再次访问。
            if (cost <= fuel) {
                answer += dfs(next, fuel - cost);
                answer %= MOD;
            }
        }

        memo[pos][fuel] = (int) answer;

        return memo[pos][fuel];
    }
}

func countRoutes(locations []int, start int, finish int, fuel int) int {
    const mod = 1_000_000_007
    n := len(locations)
    memo := make([][]int, n)
    for i := 0; i < n; i++ {
        memo[i] = make([]int, fuel+1)
        for f := 0; f <= fuel; f++ {
            memo[i][f] = -1
        }
    }

    var dfs func(pos int, fuel int) int
    dfs = func(pos int, fuel int) int {
        if memo[pos][fuel] != -1 {
            return memo[pos][fuel]
        }
        answer := 0
        // 终点先计入现在停止的路线，仍继续搜索离开后返回的路线。
        if pos == finish {
            answer = 1
        }
        for next := 0; next < n; next++ {
            // 禁止零消耗原地移动，其他城市坐标不同，油量严格下降。
            if next == pos {
                continue
            }
            cost := locations[pos] - locations[next]
            if cost < 0 {
                cost = -cost
            }
            // 油量恰好够用也能移动，同一城市可在不同剩余油量下再次访问。
            if cost <= fuel {
                answer += dfs(next, fuel-cost)
                answer %= mod
            }
        }
        memo[pos][fuel] = answer
        return answer
    }

    return dfs(start, fuel)
}

复杂度分析

设城市数为 n，初始燃油为 F。

  • 时间复杂度：$O(n^2(F+1))$，至多 $n(F+1)$ 个状态，每个状态枚举 n 个目的地。
  • 空间复杂度：缓存为 $O(n(F+1))$，每次移动至少消耗一个单位燃油，递归栈至多为 $O(F+1)$。

关键点总结

[!green]

  • 到达终点提供一种停止选择，但不取消后续离开再返回的路线。
  • 当前位置和剩余油量共同决定状态，城市可重复出现，完全相同的状态才复用结果。
  • 燃油严格下降保证递归终止，无需用城市访问标记阻止回访。

易错点总结

[!yellow]

  • 到达终点就直接返回 1，会漏掉离开后再次到达的路线。
  • 不能只按城市缓存，也不能用城市级 visited 禁止重复经过，同一城市在不同油量下有不同后续选择。
  • 不能允许原地移动，否则零代价会让状态依赖自己；其他城市坐标互异保证了剩余移动代价为正。
  • 代价等于剩余油量时也可移动，剩余零油量到达终点仍是一条合法路线。
  • 不同公开调用的坐标或终点可能变化，Java 成员缓存必须在入口重新创建，不能沿用上一次问题的状态。

相似题目

题目 难度 关联与区别
576. 出界的路径数 中等 同样在有限资源维度上累计路径，本题每跳消耗不同燃油且允许返回城市，原题每步固定消耗1。
787. K 站中转内最便宜的航班 中等 同样将位置与剩余资源组合成状态，原题最小化票价，本题累计所有燃油预算内路线。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/45191846
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！