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

  1. class Solution {
  2.     /**
  3.     记忆化搜索，cache[i][fuel]表示城市i到目的地在油量是fuel的路径数
  4.      */
  5.     int[][] cache;
  6.     int mod = (int)1e9 + 7;
  7.     public int countRoutes(int[] locations, int start, int finish, int fuel) {
  8.         int n = locations.length;
  9.         cache = new int[n][fuel + 1];
  10.         for (int i = 0; i < n; ++i) 
  11.             Arrays.fill(cache[i], -1);
  12.         return dfs(locations, start, finish, fuel);
  13.     }
  15.     private int dfs(int[] loc, int u, int end, int fuel) {
  16.         //如果缓存器中已有答案，直接返回
  17.         if (cache[u][fuel] != -1) {
  18.             return cache[u][fuel];
  19.         }
  20.         int n = loc.length;
  21.         //base case 1 : 当油量为0,且不是终点的时候
  22.         if (fuel == 0 && u != end) {
  23.             cache[u][fuel] = 0;
  24.             return 0;
  25.         }
  26.         //base case 2 : 当油量不为0,但是到不了任何地方的情况
  27.         boolean flag = false;
  28.         // for (int i = 0; i < n; ++i) {
  29.         //     if (u != i) {
  31.         //         }
  32.         //     }
  33.         // }
  34.         int nd = Math.abs(loc[u] - loc[end]);
  35.         if (fuel >= nd) {
  36.             flag = true;
  37.         }
  38.         if (fuel != 0 && !flag) {
  39.             cache[u][fuel] = 0;
  40.             return 0;
  41.         }
  42.         //当是终点时，为1条有效路径,因为可以经过终点
  43.         int sum = u == end ? 1 : 0;
  44.         for (int i = 0; i < n; ++i) {
  45.             if (i != u) {
  46.                 int need = Math.abs(loc[i] - loc[u]);
  47.                 if (fuel >= need) {
  48.                     sum += dfs(loc, i, end, fuel - need);
  49.                     sum %= mod;
  50.                 }
  51.             }
  52.         }
  53.         cache[u][fuel] = sum;
  54.         return sum;
  55.     }
  56. }

优化：简化base case如果不能一步到目的地，那么也不能多次到

  1. class Solution {
  2.     /**
  3.     记忆化搜索，cache[i][fuel]表示城市i到目的地在油量是fuel的路径数
  4.      */
  5.     int[][] cache;
  6.     int mod = (int)1e9 + 7;
  7.     public int countRoutes(int[] locations, int start, int finish, int fuel) {
  8.         int n = locations.length;
  9.         cache = new int[n][fuel + 1];
  10.         for (int i = 0; i < n; ++i) 
  11.             Arrays.fill(cache[i], -1);
  12.         return dfs(locations, start, finish, fuel);
  13.     }
  15.     private int dfs(int[] loc, int u, int end, int fuel) {
  16.         //如果缓存器中已有答案，直接返回
  17.         if (cache[u][fuel] != -1) {
  18.             return cache[u][fuel];
  19.         }
  20.         int n = loc.length;
  21.         //如果不能一次到，直接返回0
  22.         int nd = Math.abs(loc[u] - loc[end]);
  23.         if (nd > fuel) {
  24.             cache[u][fuel] = 0;
  25.             return 0;
  26.         }
  27.         // //base case 1 : 当油量为0,且不是终点的时候
  28.         // if (fuel == 0 && u != end) {
  29.         //     cache[u][fuel] = 0;
  30.         //     return 0;
  31.         // }
  32.         // //base case 2 : 当油量不为0,但是到不了任何地方的情况
  33.         // boolean flag = false;
  34.         // // for (int i = 0; i < n; ++i) {
  35.         // //     if (u != i) {
  37.         // //         }
  38.         // //     }
  39.         // // }
  40.         // int nd = Math.abs(loc[u] - loc[end]);
  41.         // if (fuel >= nd) {
  42.         //     flag = true;
  43.         // }
  44.         // if (fuel != 0 && !flag) {
  45.         //     cache[u][fuel] = 0;
  46.         //     return 0;
  47.         // }
  48.         //当是终点时，为1条有效路径,因为可以经过终点
  49.         int sum = u == end ? 1 : 0;
  50.         for (int i = 0; i < n; ++i) {
  51.             if (i != u) {
  52.                 int need = Math.abs(loc[i] - loc[u]);
  53.                 if (fuel >= need) {
  54.                     sum += dfs(loc, i, end, fuel - need);
  55.                     sum %= mod;
  56.                 }
  57.             }
  58.         }
  59.         cache[u][fuel] = sum;
  60.         return sum;
  61.     }
  62. }

dp

  1. class Solution {
  2.     /**
  3.     f[i][j] 表示当前位置是i， 到达目的地，油量是j的路径数量
  4.     f[i][j] = f[i][j] + f[k][j - need];
  5.      */
  6.     int mod = (int)1e9 + 7;
  7.     public int countRoutes(int[] locations, int start, int finish, int fuel) {
  8.         int n = locations.length;
  9.         int[][] f = new int[n][fuel + 1];
  10.         //如果本身就是目的地，那么都是1
  11.         for (int i = 0; i <= fuel; ++i) f[finish][i] = 1;
  12.         //先从小到大枚举油量
  13.         for (int cur = 0; cur <= fuel; ++cur) 
  14.             for (int i = 0; i < n; ++i) 
  15.                 for (int j = 0; j < n; ++j) {
  16.                     if (i != j) {
  17.                         int need = Math.abs(locations[i] - locations[j]); 
  18.                         if (need <= cur) {
  19.                             f[i][cur] += f[j][cur - need];
  20.                             f[i][cur] %= mod;
  21.                         }
  22.                     }
  23.                 }
  24.         return f[start][fuel];
  25.     }
  26. }