您现在的位置是：首页 >技术交流 >从零学算法网站首页技术交流

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

• 题号：1575
• 之前是用了 dfs 的记忆化搜索 上一种解法
• 但是其实记忆化搜索是可以改为使用 dp(dynamic plan) 的。重点就在于看 dfs 的入参：城市 ls，当前位置 u，终点 end，剩余油量 fuel

•   /**
     * 计算「路径数量」
     * @param ls 入参 locations
     * @param u 当前所在位置（ls 的下标）
     * @param end 目标哦位置（ls 的下标）
     * @param fuel 剩余油量
     * @return 在位置 u 出发，油量为 fuel 的前提下，到达 end 的「路径数量」
     */
    int dfs(int[] ls, int u, int end, int fuel) {
        if (cache[u][fuel] != -1) {
            return cache[u][fuel];
        }
        
        int need = Math.abs(ls[u] - ls[end]);
        if (need > fuel) {
            cache[u][fuel] = 0;
            return 0;
        }
        
        int n = ls.length;
        int sum = u == end ? 1 : 0;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                need = Math.abs(ls[i] - ls[u]);
                if (fuel >= need) {
                    sum += dfs(ls, i, end, fuel - need);
                    sum %= mod;
                }
            }
        }
        cache[u][fuel] = sum;
        return sum;
    }
  

• 其中 ls 和 end 是不变的，那就根据变量来定义状态转移方程。假定 f[i][j] 为从位置 i 出发剩余 j 油量时的可行路径数量，那么我只需要得到 f[start][fuel] 即可。dfs 的主逻辑为从 u 出发，看看能到达的每个下一个地点到终点有几条可行路径，也就是 dfs 中的循环累加：sum += dfs(ls, i, end, fuel - need);，那么我们的状态转移方程就为 f[i][fuel] = f[i][fuel] + f[k][fuel-need]，其中 k 为下一个地点的坐标，need 为到达下一地点所需油量。（看完题解的个人理解）

•   int mod = 1000000007;
    public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
  
        // f[i][j] 代表从位置 i 出发，当前油量为 j 时，到达目的地的路径数
        int[][] f = new int[n][fuel + 1];
        
        // 对于本身位置就在目的地的状态，路径数为 1
        // 对应于 dfs 中的  int sum = u == end ? 1 : 0;
        for (int i = 0; i <= fuel; i++) f[end][i] = 1;
  
        // 从状态转移方程可以发现 f[i][fuel]=f[i][fuel]+f[k][fuel-need]
        // 在计算 f[i][fuel] 的时候依赖于 f[k][fuel-need]
        // 其中 i 和 k 并无严格的大小关系
        // 而 fuel 和 fuel-need 具有严格大小关系：fuel >= fuel-need
        // 因此需要先从小到大枚举油量
        for (int cur = 0; cur <= fuel; cur++) {
        	// 这两重循环就是枚举了从 ls 的每个点到其他点的情况，
            for (int i = 0; i < n; i++) {
                for (int k = 0; k < n; k++) {
                    if (i != k) {
                        int need = Math.abs(ls[i] - ls[k]);
                        if (cur >= need) {
                            f[i][cur] += f[k][cur-need];
                            f[i][cur] %= mod;
                        }
                    }
                }
            }
        }
        return f[start][fuel];
    }