DFS解法
- 首先来理解一下题意，给定起始城市的下标，目标城市的下标，以及拥有的汽油 fuel，且每个城市可以无限次经过（当然要保证汽油足够的情况下），求从起始城市到目标城市的路径总数。
- 从直观上来看，这题可以用搜索解决，但是由于问题规模（城市的数量 <= 200），所以我们引入备忘录来避免搜索重复的子问题。
cache[u][fuel]：代表在当前城市 u 且汽油总量为 fuel 的情况下，到达终点的路径总数。
- 接下来我们尝试设计 DFS 的函数头，
dfs(int[] locations, int u, int end, int fule)，其中数组 locations 存储着每个城市的位置，u 代表当前所在的城市，end 代表我们的目的地，fuel 为当前剩余的汽油总量。 - 考虑递归出口，从朴素的角度出发，当汽油为0，且所在城市不是目的地，就说明不能到达了，所以有第一种情况：
Base Case 1 : fuel == 0 && u != end，同时还存在一种情况，就是汽油不为0，但是剩余的汽油哪里也去不了了，这时也到达不了终点。Base Case 2 : fuel != 0 && !hasNext。(注：hasNext 需要单独计算)。代码如下： ```java // 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;
}
5. 接下来就是搜索的主体内容了，根据 u 计算其他城市的距离，如果能够到其他城市 i，就累加（起点为i，汽油为fuel - need）的情况。（注：need 为城市 u 到城市 i 所需）。详细代码如下：```java// 计算油量为 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;
- 时间复杂度：最坏情况下共有 n fuel 个状态需要计算，且每个状态计算需要 O(n) 的时间复杂度，所以整体复杂度为 O(n n * fuel)。
空间复杂度：O(n n 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;
}
}
DP解法
状态定义：dp[i][cur] 代表当前城市 i 且汽油为 cur的情况下，到达终点城市 finish 的路径总数
问题目标：dp[start][fuel]
状态转移：dp[i][cur] += dp[k][cur - need] if i != k && cur - need >= 0, k = 0, 1, ... , n-1
在计算状态转移时，dp[i][cur] 依赖于 dp[k][cur - need]，意味着我们先枚举油量这一维（注意这跟背包的容量的枚举不一样）。
状态初始化：终点位置全部加1，无论汽油量的多少，即 dp[finish][~] = 1
时间复杂度：O(n n fuel)
空间复杂度：O(n n fuel)
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];
}
}
若有收获，就点个赞吧
0 人点赞
