leetcode刷题（127）——1575. 统计所有可行路径

老马的编程之旅

发布于 2022-11-16 13:29:30

2090

发布于 2022-11-16 13:29:30

给你一个互不相同的整数数组，其中 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] <= 109 所有 locations 中的整数互不相同。 0 <= start, finish < locations.length 1 <= fuel <= 200

数据范围也只有，很多同学会想到 DFS。

但是我们之前讲过，单纯的 DFS 由于是指数级别的复杂度，通常数据范围不出超过 30。

不过，「记忆化搜索」可以。

记忆化搜索

如果要实现 DFS 的话，通常有以下几个步骤：

设计好递归函数的「入参」和「出参」设置好递归函数的出口（Base Case）编写「最小单元」处理逻辑对于大多数的 DFS 来说，第 1 步和第 3 步都很好实现，而找 Base Case 通常是三部曲中最难的。

以本题为例，我们来剖析一下「该如何找 Base Case」。

首先要明确，所谓的找 Base Case，其实是在确定什么样的情况下，算一次有效/无效。

对于本题，找 Base Case 其实就是在确定：什么样的情况下，算是 0 条路径；什么样的情况下，算是 1 条路径。

然后再在 DFS 过程中，不断的累加有效情况（算作路径数量为 1）的个数作为答案。

这是 DFS 的本质，也是找 Base Case 的思考过程。

回到本题，对于有效情况的确立，十分简单直接，如果我们当前所在的位置就是目的地的话，那就算成是一条有效路径，我们可以对路径数量进行 +1。

那么如何确立无效情况呢？

一个直观的感觉是当油量消耗完，所在位置又不在，那么就算走到头了，算是一次「无效情况」，可以终止递归。

逻辑上这没有错，但是存在油量始终无法为零的情况。

考虑以下样例数据：

locations = [0,2,2,2], 
start = 0, 
finish = 3, 
fuel = 1

我们当前位置在 0，想要到达 3，但是油量为 1，无法移动到任何位置。

也就是如果我们只考虑fuel=0 作为 Base Case 的话，递归可能无法终止。

因此还要增加一个限制条件：油量不为 0，但无法再移动到任何位置，也算是一次「无效情况」，可以终止递归。

到这里，我们已经走完「DFS 的三部曲」了，然后由于本题的数据范围超过了 30，我们需要为 DFS 添加「记忆化搜索」。

缓存器的设计也十分简单，使用二维数组 cache[][]进行记录即可。

我们用 cache[i][fuel] 代表从位置出发，当前剩余的油量为fuel 的前提下，到达目标位置的「路径数量」。

之所以能采取「缓存中间结果」这样的做法，是因为「在 i 和 fuel 确定的情况下，其到达目的地的路径数量是唯一确定的」。

class Solution {
    int mod = 1000000007;
    
    // 缓存器：用于记录「特定状态」下的结果
    // cache[i][fuel] 代表从位置 i 出发，当前剩余的油量为 fuel 的前提下，到达目标位置的「路径数量」
    int[][] cache;
    
    public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
        
        // 初始化缓存器
        // 之所以要初始化为 -1
        // 是为了区分「某个状态下路径数量为 0」和「某个状态尚未没计算过」两种情况
        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        
        return dfs(ls, start, 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 n = ls.length;
        // base case 1：如果油量为 0，且不在目标位置
        // 将结果 0 写入缓存器并返回
        if (fuel == 0 && u != end) {
            cache[u][fuel] = 0;
            return 0;
        } 
        
        // base case 2：油量不为 0，且无法到达任何位置
        // 将结果 0 写入缓存器并返回
        boolean hasNext = false;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                int need = Math.abs(ls[u] - ls[i]);    
                if (fuel >= need) {
                    hasNext = true;
                    break;
                }
            }
        }
        if (fuel != 0 && !hasNext) {
            int a= cache[u][fuel] = u==end?1:0;
            return a;
        }
        
        // 计算油量为 fuel，从位置 u 到 end 的路径数量
        // 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
        int sum = u == end ? 1 : 0;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                int 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;
    }
}

简化 Base Case (挖掘性质)

我们「无效情况」的 Base Case 是可以进一步简化的。

考虑一个问题：如果我们从某个位置 i 出发，不能一步到达目标位置的话，有可能使用多步到达目标位置吗？

也就是一步不行的话，多步可以吗？

答案是不可以。

假设我们当前位置的 location[i] 为 a，目标位置的 location[finish] 为 b，两者差值的绝对值为need ，而当前油量是 fuel。

不能一步到达，说明 need>fuel。

而我们每次移动到新的位置，消耗的油量 cost 都是两个位置的差值绝对值。

正因为 cost>=0，因此我们移动到新位置后的油量 fuel’<=fuel。

换句话说，即使从位置 i 移动到新位置，也无法改变 need > fuel 的性质。

如果我们在某个位置 u 出发，不能一步到达目的地 finish，将永远无法到达目的地。

class Solution {
    int mod = 1000000007;
    
    // 缓存器：用于记录「特定状态」下的结果
    // cache[i][fuel] 代表从位置 i 出发，当前剩余的油量为 fuel 的前提下，到达目标位置的「路径数量」
    int[][] cache;
    
    public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
        
        // 初始化缓存器
        // 之所以要初始化为 -1
        // 是为了区分「某个状态下路径数量为 0」和「某个状态尚未没计算过」两种情况
        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        
        return dfs(ls, start, 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];
        }
        
        // 如果一步到达不了，说明从位置 u 不能到达 end 位置
        // 将结果 0 写入缓存器并返回
        int need = Math.abs(ls[u] - ls[end]);
        if (need > fuel) {
            cache[u][fuel] = 0;
            return 0;
        }
        
        int n = ls.length;
        // 计算油量为 fuel，从位置 u 到 end 的路径数量
        // 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
        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;
    }
}