统计所有可行路径

难度: Hard

给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量

每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。

请注意， fuel 任何时刻都不能为负，且你可以经过任意城市超过一次（包括 start 和 finish ）。

请你返回从 start 到 finish 所有可能路径的数目。

由于答案可能很大，请将它对 10^9 + 7 取余后返回。

示例 1：

输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
输出：4
解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

示例 2：

输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
输出：5
解释：以下为所有可能的路径：
1 -> 0，使用汽油量为 fuel = 1
1 -> 2 -> 0，使用汽油量为 fuel = 5
1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5

示例 3：

输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
输出：0
解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。

提示：

2 <= locations.length <= 100
1 <= locations[i] <= 10⁹
所有 locations 中的整数 互不相同 。
0 <= start, finish < locations.length
1 <= fuel <= 200

Submission

运行时间: 145 ms

内存: 17.2 MB

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        mod = 10**9 + 7

        n = len(locations)
        startPos = locations[start]
        finishPos = locations[finish]
        locations.sort()
        start = locations.index(startPos)
        finish = locations.index(finishPos)

        dpL = [[0] * (fuel + 1) for _ in range(n)]
        dpR = [[0] * (fuel + 1) for _ in range(n)]
        dpL[start][0] = dpR[start][0] = 1
        
        for used in range(fuel + 1):
            for city in range(n - 2, -1, -1):
                if (delta := locations[city + 1] - locations[city]) <= used:
                    dpL[city][used] = ((0 if used == delta else dpL[city + 1][used - delta]) * 2 + dpR[city + 1][used - delta]) % mod
            for city in range(1, n):
                if (delta := locations[city] - locations[city - 1]) <= used:
                    dpR[city][used] = ((0 if used == delta else dpR[city - 1][used - delta]) * 2 + dpL[city - 1][used - delta]) % mod

        ans = sum(dpL[finish]) + sum(dpR[finish])
        if start == finish:
            ans -= 1
        return ans % mod

Explain

这个题解采用动态规划的方法来解决。首先对城市位置进行排序，并且重新定位起始和结束城市的索引。这样可以利用位置的有序性来简化状态转移。定义两个动态规划数组 dpL 和 dpR，分别表示从左向右和从右向左计算到达某个城市的路径数。dpL[i][f] 表示从起点到位置i使用f单位燃料的路径数，dpR[i][f] 则是相反方向的计数。通过遍历每一步可能使用的燃料量和城市，我们更新两个DP数组。这种方法不断地根据前一个城市的状态来更新当前城市的状态，利用了前后城市距离的具体值来减少燃料，并在途中累加可能的路径。最后，将两个DP数组在目标城市的所有燃料状态下的值相加，得到最终结果。如果起始城市和目标城市是同一个，则还需调整最终计数，因为算法中计算了从起点到起点的一个额外路径。

时间复杂度: O(n * f)

空间复杂度: O(n * f)

# 定义 Solution 类

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        mod = 10**9 + 7  # 用于取余的数

        # 初始化和处理位置信息
        n = len(locations)
        startPos = locations[start]
        finishPos = locations[finish]
        locations.sort()
        start = locations.index(startPos)
        finish = locations.index(finishPos)

        # 初始化动态规划表
        dpL = [[0] * (fuel + 1) for _ in range(n)]
        dpR = [[0] * (fuel + 1) for _ in range(n)]
        dpL[start][0] = dpR[start][0] = 1

        # 动态规划处理
        for used in range(fuel + 1):
            for city in range(n - 2, -1, -1):
                if (delta := locations[city + 1] - locations[city]) <= used:
                    dpL[city][used] = ((0 if used == delta else dpL[city + 1][used - delta]) * 2 + dpR[city + 1][used - delta]) % mod
            for city in range(1, n):
                if (delta := locations[city] - locations[city - 1]) <= used:
                    dpR[city][used] = ((0 if used == delta else dpR[city - 1][used - delta]) * 2 + dpL[city - 1][used - delta]) % mod

        # 结果统计
        ans = sum(dpL[finish]) + sum(dpR[finish])
        if start == finish:
            ans -= 1  # 如果起始和结束城市相同，调整计数
        return ans % mod

Explore

动态规划数组 dpL 和 dpR 通过逐步计算每种燃料使用情况下从起点到各个城市的路径数量，确保了能够覆盖从任一起点到任一终点的所有可能路径。dpL 从左向右计算，负责记录从起点开始向右移动到达每个城市时各种燃料情况的路径数量；dpR 从右向左计算，记录从起点开始向左移动到达每个城市时的路径数量。这样，无论目标城市在起点的左边还是右边，都有相应的动态规划数组来记录到达该城市的所有可能路径数。

如果起始城市和目标城市是同一个，算法实际上会在初始化时将 dpL[start][0] 和 dpR[start][0] 设为 1，意味着考虑了从起点到起点的路径。因此，当最后统计所有路径时，这一路径会被重复计算一次。为了纠正这一重复计数，需要在最终结果中减去1。这样调整是为了确保路径计数的准确性，避免因初始化导致的重复计数问题。

在更新 dpL 和 dpR 数组时，同时考虑从左到右和从右到左的情况能够有效处理城市间的双向移动。这种双向更新允许算法在任一方向上捕捉路径，并根据当前城市和燃料消耗来调整下一个可能的移动方向。例如，当城市间距离较小并且剩余燃料较多时，可以通过双向更新来探索更多的路径可能性。这种方法增强了动态规划的灵活性和覆盖面，使其能够更好地适应不同的燃料和距离情况，从而找到所有可能的到达路径。

在燃料为0或非常少的情况下，动态规划的设计保证了算法的正确性。dpL 和 dpR 在初始化时，将 dpL[start][0] 和 dpR[start][0] 设置为 1，表明无需消耗燃料即可停留在起点。对于其他城市，如果没有足够的燃料到达某个城市，则对应的 dpL[i][f] 和 dpR[i][f] 保持为0，表示无法到达。这种处理确保了即使在燃料非常少的情况下，算法也能正确反映从起点到其他城市的可达性。