What is the main pattern used in Count All Possible Routes?

This problem uses state transition dynamic programming, with states defined by current city and remaining fuel, and transitions representing moving to other cities.

Can I visit the same city multiple times?

Yes, revisiting cities is allowed as long as fuel remains non-negative, which is critical for counting all possible routes correctly.

How do I avoid recalculating the same state?

Use memoization by storing the number of routes for each (city, remaining fuel) state, which reduces redundant computation.

What happens if fuel is insufficient for a direct move?

Such moves are invalid and should not be counted; only transitions where remaining fuel stays non-negative are considered.

Is dynamic programming necessary for this problem?

Yes, without DP the exponential number of possible routes leads to timeouts; DP ensures efficient state exploration and correct counting.

#1575

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计所有可行路径

给你一个互不相同的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start ， finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 ，并移动到城市 …

数组动态规划记忆化

题目描述

给你一个 互不相同 的整数数组，其中 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

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i, k)$ ，表示从城市 $i$ 出发，剩余汽油量为 $k$ 时，到达目的地 $finish$ 的路径数。那么答案就是 $dfs(start, fuel)$ 。

函数 $dfs(i, k)$ 的计算过程如下：

如果 $k \lt |locations[i] - locations[finish]|$ ，那么返回 $0$ 。
如果 $i = finish$ ，那么答案路径数初始时为 $1$ ，否则为 $0$ 。
然后，我们遍历所有城市 $j$ ，如果 $j \ne i$ ，那么我们可以从城市 $i$ 移动到城市 $j$ ，此时剩余汽油量为 $k - |locations[i] - locations[j]|$ ，那么我们可以将答案路径数加上 $dfs(j, k - |locations[i] - locations[j]|)$ 。
最后，我们返回答案路径数。

为了避免重复计算，我们可以使用记忆化搜索。

时间复杂度 $O(n^2 \times m)$ ，空间复杂度 $O(n \times m)$ 。其中 $n$ 和 $m$ 分别是数组 $locations$ 和 $fuel$ 的大小。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def countRoutes(
        self, locations: List[int], start: int, finish: int, fuel: int
    ) -> int:
        @cache
        def dfs(i: int, k: int) -> int:
            if k < abs(locations[i] - locations[finish]):
                return 0
            ans = int(i == finish)
            for j, x in enumerate(locations):
                if j != i:
                    ans = (ans + dfs(j, k - abs(locations[i] - x))) % mod
            return ans

        mod = 10**9 + 7
        return dfs(start, fuel)

speed

复杂度分析

指标	值
时间	and space complexity depend on the number of unique states, bounded by number of cities times fuel capacity. Memoization reduces exponential recursion to O(n * fuel) states, each potentially checking O(n) transitions.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on memoizing (city, fuel) states rather than tracking exact paths.
question_mark
Recognize revisiting cities is allowed and must be handled without double-counting errors.
question_mark
Check edge cases where fuel is insufficient for even the direct move from start to finish.

warning

常见陷阱

外企场景

error
Failing to memoize states, causing exponential timeouts.
error
Subtracting fuel incorrectly or allowing negative fuel states.
error
Ignoring that visiting the same city multiple times is valid and needed for some routes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute routes with a maximum number of stops instead of fuel limit.
arrow_right_alt
Count only routes that visit each city at most once while respecting fuel constraints.
arrow_right_alt
Optimize for minimal total fuel to reach finish while counting only feasible paths.

help

常见问题

外企场景

继续练习

#1569 将子数组重新排序得到同一个二叉搜索树的方案数 #1444 切披萨的方案数 #1728 猫和老鼠 II