从零学算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了从零学算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1575.给你一个互不相同的整数数组，其中 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文章来源地址https://www.toymoban.com/news/detail-455958.html

直接上题号吧，不是我能解的：1575
他人题解：通常情况下，会给定一个形状的地图，然后给定起点（不给你就枚举每个起点就好）终点，然后根据具体规则（比如只能往上和往右）走，有起点和规则你就算出最优解即可。但是这题没有告诉你怎么走，甚至到达终点以后，油量足够的话还能继续走。那么这时就需要记忆化搜索了，设置缓存器 cache[i][fuel] ，代表从位置 i 出发，当前剩余的油量为 fuel 的前提下，到达目标位置的「路径数量」(个人理解，这就是可以得到所有不重复且不遗漏的所有情况的一种设置，我只想到 cache[i] 代表从 i 出发到终点有多少路径，然而这样就忽略了油量这个条件)。然后 dfs 的基本结构我就引用一下

设计好递归函数的「入参」和「出参」

设置好递归函数的出口（Base Case）

编写「最小单元」处理逻辑

第一点好说，题目给的几个输入：所有城市，起点，终点以及油量（先用着，不够再加），Base Case 在本题具体体现为怎么样算一条有效路径，怎么样就无效了，最小单元处理逻辑的话直接循环累加当前点到其他点后到终点的路径数（看代码好理解一点）。首先无效情况，当前点如果到不了终点，那肯定不可能先去其他点再到终点(三角形两边之和大于第三边，也就是说最少也需要起点直达终点的油量)，然后循环累加，记得当前位置如果在终点说明已经有一条有效路径。

  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 cur, int end, int fuel){
      int need = Math.abs(ls[cur]-ls[end]);
      if(need > fuel){
          cache[cur][fuel] = 0;
          return 0;
      }
      int n = ls.length;
      // 计算油量为 fuel，从位置 u 到 end 的路径数量
      // 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
      int sum = cur == end? 1 : 0;
      // 从这个结点开枝散叶了，每次都看看去了其他任何能到达的点以后还能不能得到有效路径
      for(int i=0;i<n;i++){
          if(i == cur) continue;
          need = Math.abs(ls[i]-ls[cur]);
          if(need <= fuel){
          	// 
              sum += dfs(ls,i,end,fuel-need);
              sum %= mod;
          }
      }
      cache[cur][fuel] = sum;
      return sum;
  }