Hard

题目描述

给你一个由不同正整数组成的数组 locations，其中 locations[i] 表示第 i 个城市的位置。同时给你 start、finish 和 fuel 分别表示出发城市、目的地城市和初始燃料数量。

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

请注意，燃料不能变成负数，并且你可以经过任何城市超过一次（包括 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, 用去 1 单位燃料
1 -> 2 -> 0, 用去 5 单位燃料
1 -> 2 -> 1 -> 0, 用去 5 单位燃料
1 -> 0 -> 1 -> 0, 用去 3 单位燃料
1 -> 0 -> 1 -> 0 -> 1 -> 0, 用去 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^9
  • locations 中的所有整数互不相同
  • 0 <= start, finish < locations.length
  • 1 <= fuel <= 200

解题思路

思路分析

这是一道经典的动态规划问题。我们需要计算从起始城市到目标城市的所有可能路径数量，其中路径的长度受燃料限制。

核心思想是使用记忆化递归或二维动态规划。状态定义为：dp[city][fuel] 表示当前在城市 city，剩余燃料为 fuel 时，能够到达终点城市的路径数量。

状态转移方程：

  • 如果当前城市就是终点，那么至少有一种路径（停留在终点）
  • 否则，我们可以尝试从当前城市移动到其他任意城市，前提是燃料足够

对于每个城市 j（j ≠ 当前城市），如果剩余燃料 >= |locations[current] - locations[j]|，那么我们可以移动到城市 j，剩余燃料变为 fuel - cost，路径数累加到结果中。

优化要点：

  1. 使用记忆化避免重复计算
  2. 边界条件：如果当前城市是终点，结果至少为1
  3. 剪枝：如果燃料不足以到达任何其他城市，提前返回

时间复杂度主要取决于状态数量（城市数 × 燃料数）和状态转移（需要遍历所有城市）。

代码实现

class Solution {
public:
    const int MOD = 1000000007;
    vector<vector<int>> memo;
    vector<int> locations;
    int finish;
    
    int dfs(int city, int fuel) {
        if (memo[city][fuel] != -1) {
            return memo[city][fuel];
        }
        
        long long result = 0;
        
        // 如果当前在终点，至少有一种路径
        if (city == finish) {
            result = 1;
        }
        
        // 尝试移动到其他城市
        for (int j = 0; j < locations.size(); j++) {
            if (j != city) {
                int cost = abs(locations[city] - locations[j]);
                if (fuel >= cost) {
                    result = (result + dfs(j, fuel - cost)) % MOD;
                }
            }
        }
        
        return memo[city][fuel] = result;
    }
    
    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        this->locations = locations;
        this->finish = finish;
        memo.assign(locations.size(), vector<int>(fuel + 1, -1));
        return dfs(start, fuel);
    }
};

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        MOD = 1000000007
        memo = {}
        
        def dfs(city, remaining_fuel):
            if (city, remaining_fuel) in memo:
                return memo[(city, remaining_fuel)]
            
            result = 0
            
            # 如果当前在终点，至少有一种路径
            if city == finish:
                result = 1
            
            # 尝试移动到其他城市
            for j in range(len(locations)):
                if j != city:
                    cost = abs(locations[city] - locations[j])
                    if remaining_fuel >= cost:
                        result = (result + dfs(j, remaining_fuel - cost)) % MOD
            
            memo[(city, remaining_fuel)] = result
            return result
        
        return dfs(start, fuel)

public class Solution {
    private const int MOD = 1000000007;
    private int[,] memo;
    private int[] locations;
    private int finish;
    
    public int CountRoutes(int[] locations, int start, int finish, int fuel) {
        this.locations = locations;
        this.finish = finish;
        memo = new int[locations.Length, fuel + 1];
        
        // 初始化memo为-1
        for (int i = 0; i < locations.Length; i++) {
            for (int j = 0; j <= fuel; j++) {
                memo[i, j] = -1;
            }
        }
        
        return DFS(start, fuel);
    }
    
    private int DFS(int city, int remainingFuel) {
        if (memo[city, remainingFuel] != -1) {
            return memo[city, remainingFuel];
        }
        
        long result = 0;
        
        // 如果当前在终点，至少有一种路径
        if (city == finish) {
            result = 1;
        }
        
        // 尝试移动到其他城市
        for (int j = 0; j < locations.Length; j++) {
            if (j != city) {
                int cost = Math.Abs(locations[city] - locations[j]);
                if (remainingFuel >= cost) {
                    result = (result + DFS(j, remainingFuel - cost)) % MOD;
                }
            }
        }
        
        return memo[city, remainingFuel] = (int)result;
    }
}

var countRoutes = function(locations, start, finish, fuel) {
    const MOD = 1e9 + 7;
    const n = locations.length;
    const memo = new Map();
    
    function dfs(current, remainingFuel) {
        const key = `${current},${remainingFuel}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        let count = 0;
        if (current === finish) {
            count = 1;
        }
        
        for (let next = 0; next < n; next++) {
            if (next === current) continue;
            
            const fuelCost = Math.abs(locations[current] - locations[next]);
            if (remainingFuel >= fuelCost) {
                count = (count + dfs(next, remainingFuel - fuelCost)) % MOD;
            }
        }
        
        memo.set(key, count);
        return count;
    }
    
    return dfs(start, fuel);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
记忆化递归O(n² × fuel)O(n × fuel)

其中：

  • n 为城市数量，fuel 为初始燃料数量
  • 时间复杂度：有 n × fuel 个状态，每个状态需要遍历 n 个城市进行转移
  • 空间复杂度：记忆化数组需要 O(n × fuel) 空间，递归栈深度最多为 fuel