1575-统计所有可行路径(Count All Possible Routes)

原文链接: https://leetcode-cn.com/problems/count-all-possible-routes

英文原文

You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.

At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.

Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).

Return the count of all possible routes from start to finish. Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
Output: 4
Explanation: The following are all possible routes, each uses 5 units of fuel:
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

Example 2:

Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6
Output: 5
Explanation: The following are all possible routes:
1 -> 0, used fuel = 1
1 -> 2 -> 0, used fuel = 5
1 -> 2 -> 1 -> 0, used fuel = 5
1 -> 0 -> 1 -> 0, used fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5

Example 3:

Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3
Output: 0
Explanation: It's impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.

Example 4:

Input: locations = [2,1,5], start = 0, finish = 0, fuel = 3
Output: 2
Explanation: There are two possible routes, 0 and 0 -> 1 -> 0.

Example 5:

Input: locations = [1,2,3], start = 0, finish = 2, fuel = 40
Output: 615088286
Explanation: The total number of possible routes is 2615088300. Taking this number modulo 10^9 + 7 gives us 615088286.

Constraints:

2 <= locations.length <= 100
1 <= locations[i] <= 10⁹
All integers in locations are distinct.
0 <= start, finish < locations.length
1 <= fuel <= 200

中文题目

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

示例 4 ：

输入：locations = [2,1,5], start = 0, finish = 0, fuel = 3
输出：2
解释：总共有两条可行路径，0 和 0 -> 1 -> 0 。

示例 5：

输入：locations = [1,2,3], start = 0, finish = 2, fuel = 40
输出：615088286
解释：路径总数为 2615088300 。将结果对 10^9 + 7 取余，得到 615088286 。

提示：

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

通过代码

高赞题解

前言

今天是我们讲解动态规划专题中的 路径问题的第八天。

昨天我向你讲解了 1575. 统计所有可行路径的「记忆化搜索」解法。

今天我们将讲解「1575. 统计所有可行路径」中的「动态规划」解法。

另外，我想强调对于任何算法题，无论难度 tag 是什么。在没见过同类题时，是很难想到怎么做的。因此做不出十分正常，大家千万不要因此失去信心。

做算法是一个增加自信的过程，而不是失去信心的过程。

一道题原本完全没有思路，看了题解之后理解了。

下次遇到能做出来，或者不至于毫无思路。这本身就已经是一种进步了 ~

所以大家加油呀💪 ~

最后，我在文章结尾处列举了我所整理的关于路径问题的相关题目。

路径问题我会按照编排好的顺序进行讲解（一天一道）。

你也先可以尝试做做，也欢迎你向我留言补充，你觉得与路径相关的 DP 类型题目 ~

回顾

本题的「记忆化搜索」部分在这里：1575. 统计所有可行路径【上集】

昨天，我跟你提到过了今天的内容：

如何将「记忆化搜索」改成「动态规划」。
如果 $locations.length$ 的数据范围从 $10^2$ 改为 $10^4$，如何求解。

我们今天先来讲解第 1 点，第 2 点会放到一个单独的【番外篇】。

目的是为了控制每篇文章字数在 4k 以内，不至于一下子灌输太多内容。

动态规划

我先看下上一节「记忆化搜索」中的代码。

可以着重留意 DFS 部分的代码：

class Solution {
    int mod = 1000000007;
    int[][] cache;
    public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
        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 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;
    }
}

接下来，我将会教你如何直接将「记忆化搜索」改成「动态规划」。

使用这种技巧，你将不需要去猜「状态定义」和根据「状态定义」推导「状态转移方程」。

我们重点关注下我们的 DFS 方法签名设计：

int dfs(int[] ls, int u, int end, int fuel) {}

其中，$ls$ 参数和 $end$ 参数分别代表源输入的 $locations$ 和 $finish$，在整个 DFS 过程都不会变化，属于不变参数。

而 $u$ 参数和 $fuel$ 参数则是代表了 DFS 过程中的当前位置和当前油量，属于变化参数。

因此我们可以定一个 $f[][]$ 二维数组，来分别表示两个可变参数。

第一维代表当前位置（对应 $locations$ 数组的下标），第二维代表当前剩余油量。

二维数组中存储的就是我们的 DFS 方法的返回值（路径数量）。

同时结合题意，不难得知维度的取值范围：

第一维的取值范围为 $[0, locations.length)$
第二维的取值范围为 $[0, fuel]$

做完这一步的”翻译“工作，我们就得到了「动态规划」的「状态定义」了。

$f[i][j]$ 代表从位置 $i$ 出发，当前剩余油量为 $j$ 的前提下，到达目的地的路径数量。

不知道你是否发现，这个「状态定义」和我们「记忆化搜索」中的缓存器的定义是一致的。

接下来我们要从 DFS 中”翻译“出「状态转移方程」。

所谓的「状态转移方程」其实就是指如何从一个状态转移到另外一个状态。

而我们的 DFS 主逻辑就是完成这个转移的。

DFS 中的主逻辑很简单：枚举所有的位置，看从当前位置 $u$ 出发，可以到达的位置有哪些。

于是我们很容易就可以得出状态转移方程：

$f[i][fuel]=f[i][fuel]+f[k][fuel-need]$

$k$ 代表计算位置 $i$ 油量 $fuel$ 的状态时枚举的「下一位置」，$need$ 代表从 $i$ 到达 $k$ 需要的油量。

从状态转移方程可以发现，在计算 $f[i][fuel]$ 的时候依赖于 $f[k][fuel-need]$。

其中 $i$ 和 $k$ 并无严格的大小关系，而 $fuel$ 和 $fuel-need$ 具有严格的大小关系（$fuel \geq fuel-need$）。

因此我们需要先从小到大枚举油量这一维。

代码：

class Solution {
    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
        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++) {
            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];
    }
}

时间复杂度：最坏情况下共有 $n * fuel$ 个状态需要计算（填满整个 $cache$ 数组）。每计算一个状态需要遍历一次 $locations$ 数组，复杂度为 $O(n)$。整体复杂度为 $O(n^2 * fuel)$
空间复杂度：$O(n^2 * fuel)$

至此，我们只利用 DFS 的方法签名与主逻辑，就写出了「动态规划」解法。

我再帮你来总结一下这个过程：

1. 从 DFS 方法签名出发。分析哪些入参是可变的，将其作为 DP 数组的维度；将返回值作为 DP 数组的存储值。

2. 从 DFS 的主逻辑可以抽象中单个状态的计算方法。

其中第一点对应了「动态规划」的「状态定义」，第二点对应了「动态规划」的「状态方程转移」。

我希望你借此好好体会一下「记忆化搜索」与「动态规划」的联系。

总结

今天，我与你分享了如何直接将「记忆化搜索」改成「动态规划」，而无需关心具体的「状态定义」和「状态转移方程」。

到目前为止，我们已经掌握了两种求解「动态规划」问题的方法：

1. 根据经验猜一个「状态定义」，然后根据「状态定义」去推导一个「状态转移方程」。

2. 先写一个「记忆化搜索」解法，再将「记忆化搜索」改写成「动态规划」。

其中第一种是我们前几节（1 ~ 6）用到的方法，而第二种是我本节给你介绍的方法。

能够去猜「状态定义」或者使用「记忆化搜索」求解，都有一个大前提：问题本身具有无效性。

由于「动态规划」的状态定义猜测，是一门很讲求经验的技能。

因此对于那些你接触过的模型，我建议你使用第一种方式；

如果遇到一道你从来没接触过的题目时，我建议你先想想「记忆化搜索」该如何实现，然后反推出「动态规划」。

这里说的想想「记忆化搜索」该如何实现，不需要真正动手实现一个「记忆化搜索」解法，而只需要想清楚，如果使用「记忆化搜索」的话，我的 DFS 函数签名如何设计即可。

当搞清楚「记忆化搜索」的函数签名设计之后，「状态定义」部分基本就已经出来了，之后的「状态转移方程」就还是一样的分析方法。

当然，如果你觉得「记忆化搜索」更好实现的话，大可直接使用「记忆化搜索」求解，不一定需要将其转化为「动态规划」。

因为由「记忆化搜索」直接转过来的「动态规划」，两者复杂度是一样的。而且通常「记忆化搜索」的实现难度通常要低很多。

路径问题（目录）

62.不同路径（中等）：路径问题第一讲

63.不同路径 II（中等）：路径问题第二讲

64.最小路径和（中等）：路径问题第三讲

120.三角形最小路径和（中等）：路径问题第四讲

931.下降路径最小和（中等）：路径问题第五讲

1289.下降路径最小和 II（困难）：路径问题第六讲

1575.统计所有可行路径（困难）：路径问题第七讲（记忆化搜索）

1575.统计所有可行路径（困难）：路径问题第八讲（动态规划）

576.出界的路径数（中等）：路径问题第九讲

1301.最大得分的路径数目（困难）：路径问题第十讲

欢迎补充 ~

思考&进阶

$O(n^2 * fuel)$ 复杂度的算法只能支撑我们解决 $10^2$ 的数据，如果数据范围出到 $10^4$ 呢？

接下来我们该考虑如何优化 DP。

还是和以前一样，要想知道如何优化，先要剖析现有算法做了些什么工作：

转移 $n * fuel$ 个状态
每次状态需要枚举 $n$ 个点

通常需要转移的状态数量是无法减少的（空间复杂度会相对难优化），因此我们很难从第 1 点进行入手。

那么我们该如何优化第 2 点呢？

如果你学有余力，我建议你可以将其作为一个思考题。

如果你觉得今天内容已经够多了，也没有关系。

好好理解今天的内容就已经足够了，要知道我们今天的解法就是一道 Hard 题的标准解法。

这个优化手段涉及到「拆分集合等效转换」概念，超出了本系列课程的难度，我将作为「番外篇」进行介绍。

最后

如果有帮助到你，请给个点赞关注，让更多的人看到 ~ (“▔□▔)/

也欢迎你关注我和加入我们的「组队打卡」小群，提供写「证明」&「思路」的高质量题解

统计信息

通过次数	提交次数	AC比率
4810	8065	59.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途