C++ EASY SOLUTION WITH EXPLANATION.
Intuition & Approach\nThe code counts the number of possible routes from a start index to a finish index within a specified fuel limit using a recursive approac
# Intuition & Approach\nThe code counts the number of possible routes from a start index to a finish index within a specified fuel limit using a recursive approach with memoization. It calculates the routes by considering the fuel consumption between locations and tracks the remaining fuel. The memoization helps avoid redundant calculations, improving efficiency.\n\n\n- The approach uses a recursive solution with memoization.\n- It counts the number of possible routes from a start index to a finish index within a specified fuel limit.\n- Memoization helps avoid redundant calculations and improves efficiency.\n- The recursive function considers the current index, remaining fuel, and other parameters.\n- If the remaining fuel is negative, it returns 0 as there are no valid routes from that point.\n- It checks if the result for the current index and remaining fuel is already calculated in the `dp` array.\n- If the result is available, it returns the stored result.\n- Otherwise, it calculates the result by iterating over all locations, excluding the current index.\n- For each location, it calculates the fuel consumed to reach that location from the current index.\n- It recursively calls itself with the updated parameters and accumulates the returned results.\n- If the current index is the finish index, it adds 1 to the accumulated result.\n- The calculated result is stored in the `dp` array, and the function returns it.\n- The `countRoutes` function initializes the `dp` array with -1.\n- It calls the recursive function to calculate and return the total number of possible routes.\n- Memoization optimizes the calculation by avoiding redundant computations.\n\n\n# Complexity\n- Time complexity:\nO(n*m)\n\n- Space complexity:\nO(n*m)\n\n# Code\n```\nclass Solution {\npublic:\n    int dp[101][201];\n    int mod = 1e9+7;\n    int rec(vector<int> &locations, int idx, int finish, int fuel){\n      if(fuel<0) return 0; //Exit case.\n      long long ans = 0;\n      if(dp[idx][fuel]!=-1) return dp[idx][fuel]%mod;\n      // Now checking all the possible path.\n      for(int i = 0;i<locations.size(); i++){\n        if(i==idx) continue;\n        ans = (ans%mod +  rec(locations, i, finish, fuel-abs(locations[i]-locations[idx]))%mod)%mod;\n      }\n\n      //During return we have to is idx ==  finish.\n      if(idx==finish) return dp[idx][fuel] = (1 +  ans)%mod;\n      return dp[idx][fuel] = ans%mod;\n    }\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n       memset(dp, -1, sizeof(dp));\n       return rec(locations, start, finish, fuel); \n    }\n};\n```
['C++']