题目链接

统计所有可行路径

题目描述

image.png

实现代码

记忆化搜索 + DFS遍历实现代码：

  1. class Solution {
  2.     int mod = 1000000007;
  4.     // 缓存器：用于记录「特定状态」下的结果
  5.     // cache[i][fuel] 代表从位置 i 出发，当前剩余的油量为 fuel 的前提下，到达目标位置的「路径数量」
  6.     int[][] cache;
  8.     public int countRoutes(int[] ls, int start, int end, int fuel) {
  9.         int n = ls.length;
  11.         // 初始化缓存器
  12.         // 之所以要初始化为 -1
  13.         // 是为了区分「某个状态下路径数量为 0」和「某个状态尚未没计算过」两种情况
  14.         cache = new int[n][fuel + 1];
  15.         for (int i = 0; i < n; i++) {
  16.             Arrays.fill(cache[i], -1);
  17.         }
  19.         return dfs(ls, start, end, fuel);
  20.     }
  22.     /**
  23.      * 计算「路径数量」
  24.      * @param ls 入参 locations
  25.      * @param u 当前所在位置（ls 的下标）
  26.      * @param end 目标哦位置（ls 的下标）
  27.      * @param fuel 剩余油量
  28.      * @return 在位置 u 出发，油量为 fuel 的前提下，到达 end 的「路径数量」
  29.      */
  30.     int dfs(int[] ls, int u, int end, int fuel) {
  31.         // 如果缓存器中已经有答案，直接返回
  32.         if (cache[u][fuel] != -1) {
  33.             return cache[u][fuel];
  34.         }
  36.         int n = ls.length;
  37.         // base case 1：如果油量为 0，且不在目标位置
  38.         // 将结果 0 写入缓存器并返回
  39.         if (fuel == 0 && u != end) {
  40.             cache[u][fuel] = 0;
  41.             return 0;
  42.         } 
  44.         // base case 2：油量不为 0，且无法到达任何位置
  45.         // 将结果 0 写入缓存器并返回
  46.         boolean hasNext = false;
  47.         for (int i = 0; i < n; i++) {
  48.             if (i != u) {
  49.                 int need = Math.abs(ls[u] - ls[i]);    
  50.                 if (fuel >= need) {
  51.                     hasNext = true;
  52.                     break;
  53.                 }
  54.             }
  55.         }
  56.         if (fuel != 0 && !hasNext) {
  57.             cache[u][fuel] = u == end ? 1 : 0;
  58.             return cache[u][fuel];
  59.         }
  61.         // 计算油量为 fuel，从位置 u 到 end 的路径数量
  62.         // 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
  63.         int sum = u == end ? 1 : 0;
  64.         for (int i = 0; i < n; i++) {
  65.             if (i != u) {
  66.                 int need = Math.abs(ls[i] - ls[u]);
  67.                 if (fuel >= need) {
  68.                     sum += dfs(ls, i, end, fuel - need);
  69.                     sum %= mod;
  70.                 }
  71.             }
  72.         }
  73.         cache[u][fuel] = sum;
  74.         return sum;
  75.     }
  76. }

动态规划实现代码：

  1. class Solution {
  2.     int mod = 1000000007;
  3.     public int countRoutes(int[] ls, int start, int end, int fuel) {
  4.         int n = ls.length;
  6.         // f[i][j] 代表从位置 i 出发，当前油量为 j 时，到达目的地的路径数
  7.         int[][] f = new int[n][fuel + 1];
  9.         // 对于本身位置就在目的地的状态，路径数为 1
  10.         for (int i = 0; i <= fuel; i++) f[end][i] = 1;
  12.         // 从状态转移方程可以发现 f[i][fuel]=f[i][fuel]+f[k][fuel-need]
  13.         // 在计算 f[i][fuel] 的时候依赖于 f[k][fuel-need]
  14.         // 其中 i 和 k 并无严格的大小关系
  15.         // 而 fuel 和 fuel-need 具有严格大小关系：fuel >= fuel-need
  16.         // 因此需要先从小到大枚举油量
  17.         for (int cur = 0; cur <= fuel; cur++) {
  18.             for (int i = 0; i < n; i++) {
  19.                 for (int k = 0; k < n; k++) {
  20.                     if (i != k) {
  21.                         int need = Math.abs(ls[i] - ls[k]);
  22.                         if (cur >= need) {
  23.                             f[i][cur] += f[k][cur-need];
  24.                             f[i][cur] %= mod;
  25.                         }
  26.                     }
  27.                 }
  28.             }
  29.         }
  30.         return f[start][fuel];
  31.     }
  32. }