leetcode 1575. 统计所有可行路径

locations = [0,2,2,2], 
start = 0, 
finish = 3, 
fuel = 1

 class Solution {
	 // 缓存器：用于记录「特定状态」下的结果
	 // cache[i][fuel] 代表从位置 i 出发，当前剩余的油量为 fuel 的前提下，到达目标位置的「路径数量」
	 vector<vector<int>>  cache;
	 static constexpr int mod = 1000000007;
 public:
     int countRoutes(vector<int>& locations, int start, int finish, int fuel) 
	 {
		 int n = locations.size();
		 // 初始化缓存器
		// 之所以要初始化为 -1
		// 是为了区分「某个状态下路径数量为 0」和「某个状态尚未没计算过」两种情况
		 cache.resize(n,vector<int>(fuel+1,-1));
		 return dfs(locations, start, finish, fuel);
     }
     //ls：入参 locations      u 当前所在位置（ls 的下标）
	 //end 目标哦位置（ls 的下标）  fuel 剩余油量
	 //返回值: 在位置 u 出发，油量为 fuel 的前提下，到达 end 的「路径数量」
	 int dfs(vector<int>& ls, int u, int end, int fuel)
	 {
		 // 如果缓存器中已经有答案，直接返回
		 if (cache[u][fuel] != -1)
			 return cache[u][fuel];

		 int n = ls.size();
		 //base case 1：如果油量为 0，且不在目标位置
        // 将结果 0 写入缓存器并返回
		 if (fuel == 0 &&u != end)
		 {
			 cache[u][fuel] = 0;
			 return 0;
		 }

		 // base case 2：油量不为 0，且无法到达任何位置
		// 将结果 0 写入缓存器并返回
        //当前油量不为0，但是如果当前起点到终点最短距离所需要的油量都不够，那么直接返回0
		 int minNeed = abs(ls[u] - ls[end]);
		 if (minNeed>fuel&&fuel!=0)
		 {
			 cache[u][fuel] = 0;
			 return 0;
		 }

		 // 计算油量为 fuel，从位置 u 到 end 的路径数量
		// 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
		 int sum = (u == end) ? 1 : 0;
		 for (int i = 0; i < n; i++)
		 {
			 if (i != u)
			 {
				 int need = abs(ls[i] - ls[u]);
				 if (fuel >=need)
				 {
					 sum += dfs(ls, i, end, fuel-need);
					 sum %= mod;
				 }
			 }
		 }
		 cache[u][fuel] = sum;
		 return sum;
	 }
 };

int dfs(int[] ls, int u, int end, int fuel) {}

 class Solution {
 public:
     int countRoutes(vector<int>& locations, int start, int finish, int fuel) 
	 {
		 int n = locations.size();
		 // f[i][j] 代表从位置 i 出发，当前油量为 j 时，到达目的地的路径数
		 vector<vector<int>>  f(n, vector<int>(fuel + 1,0));
		 static constexpr int mod = 1000000007;
		 // 对于本身位置就在目的地的状态，路径数为 1
		 for (int i = 0; i <= fuel; i++) f[finish][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++)//cur表示油量大小
		 {
			 //这里暴力思路:枚举每一个位置作为起点，计算当前起点到终点的所有路径数目
			 for (int i = 0; i < n; i++)//当前位置起点
			 {
				 for (int j = 0; j < n; j++)//当前起点要到达的下一位置
				 {
					 if (i != j)//当前位置不能呆在原地不动
					 {
						 int need = abs(locations[i] - locations[j]);//当前位置到下一个位置消耗的油量
						 if (cur >= need)//当前油量能满足到达下一个位置
						 {
							 //f[i][cur] 代表从位置 i 出发，当前剩余油量为 cur 的前提下，到达目的地的路径数量。
							 //j是当前位置的下一个位置，当前位置到达目的地的路径数量应该是下一个位置到达目的地的数量加上自身到达目的地的数量
							 f[i][cur] += f[j][cur - need];
							 f[i][cur] %= mod;
						 }
					 }
				 }
			 }
         }
		 return f[start][fuel];
     }

 };

 f[i][cur] += f[j][cur - need];