动态规划/路径问题 动态规划的前置思考记忆化搜索以及如何推导基本性质来简化case
动态规划/路径问题 动态规划的前置思考记忆化搜索以及如何推导基本性质来简化case
前言
今天是我们讲解「动态规划专题」中的 路径问题 的第七天。
今天我们将会进入一个新的阶段：
我们会接触到另一种同样可以使用【动态规划】来求解，但又和前几题截然不同的【路径问题】。
另外，我在文章结尾处列举了我所整理的关于 路径问题 的相关题目。
路径问题 我会按照编排好的顺序进行讲解（一天一道）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与路径相关的 DP 类型题目 ~
题目描述
这是 LeetCode 上的「1575. 统计所有可行路径」，难度为 Hard。
给你一个 互不相同 的整数数组，其中 表示第 个城市的位置。
同时给你 ， 和 分别表示出发城市、目的地城市 和 你初始拥有的汽油总量。
每一步中，如果你在城市 ，你可以选择任意一个城市 ，满足 且 ，并移动到城市 。
从城市 移动到 消耗的汽油量为 ， 表示 的绝对值。
请注意， 任何时刻都不能为负，且你可以经过任意城市超过一次（包括 和 ）。
请你返回从 到 所有可能路径的数目。
由于答案可能很大，请将它对 + 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] <=
- 所有 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，无法移动到任何位置。
也就是如果我们只考虑 作为 Base Case 的话，递归可能无法终止。
因此还要增加一个限制条件：油量不为 0，但无法再移动到任何位置，也算是一次「无效情况」，可以终止递归。
到这里，我们已经走完「DFS 的三部曲」了，然后由于本题的数据范围超过了 30，我们需要为 DFS 添加「记忆化搜索」。
缓存器的设计也十分简单，使用二维数组 进行记录即可。
我们用 代表从位置 出发，当前剩余的油量为 的前提下，到达目标位置的「路径数量」。
之所以能采取「缓存中间结果」这样的做法，是因为「在 和 确定的情况下，其到达目的地的路径数量是唯一确定的」。
代码：
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 (挖掘性质)
到这里，这道题我们就已经可以 AC 了。
但事实上，我们「无效情况」的 Base Case 是可以进一步简化的。
考虑一个问题：如果我们从某个位置 出发，不能一步到达目标位置的话，有可能使用多步到达目标位置吗？
也就是一步不行的话，多步可以吗？
答案是不可以。
假设我们当前位置的 为 ，目标位置的 为 ，两者差值的绝对值为 ，而当前油量是 。
不能一步到达，说明 。
而我们每次移动到新的位置，消耗的油量 都是两个位置的差值绝对值。
正因为 ，因此我们移动到新位置后的油量 。
换句话说，即使从位置 移动到新位置，也无法改变 的性质。
如果我们在某个位置 出发，不能一步到达目的地 ，将永远无法到达目的地。
代码：
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;
}
}- 时间复杂度：最坏情况下共有 个状态需要计算（填满整个 数组）。每计算一个状态需要遍历一次 数组，复杂度为 。整体复杂度为
- 空间复杂度：
动态规划（进阶）
考虑到本文篇幅已经很长，所以我将本题的「动态规划」部分拆分到下一篇。
今天我希望你能好好消化一下「记忆化搜索」这种解法，这是你理解明天的「动态规划」的基础。
事实上，任何「记忆化搜索」都能改成「动态规划」。
我可以先剧透一下明天的内容：
- 如何将「记忆化搜索」改成「动态规划」
- 如果 的数据范围从 改为 ，如何求解
总结
这道题虽然也是一道「路径问题」。
但和我们前几天接触的「路径问题」不同，你可以将它理解为另外一种「路径问题」。
本题从数据范围入手，我们不难想到「记忆化搜索」。
在确定了「记忆化搜索」之后，我跟你强调了 DFS 解法的「三部曲」，以及「三部曲」中最难的「该如何找 Base Case」。
今天，我希望你能先放下「动态规划」，好好理解「记忆化搜索」。
理解清楚「记忆化搜索」，将会为明天的「动态规划」打下基础。
路径问题（目录）
62.不同路径（中等）：路径问题第一讲
63.不同路径 II（中等）：路径问题第二讲
64.最小路径和（中等）：路径问题第三讲
120.三角形最小路径和（中等）：路径问题第四讲
931.下降路径最小和（中等）：路径问题第五讲
1289.下降路径最小和 II（困难）：路径问题第六讲
1575.统计所有可行路径（困难）：本篇（记忆化搜索）
1575.统计所有可行路径（困难）：（动态规划）
576.出界的路径数（中等）
1301.最大得分的路径数目（困难）
欢迎补充 ~
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1575/1 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
