✅ Video Explanation🏆 Recursion-> Memoization|| ✅ C++ || Simple and Very Easy to understant
Intuition\n Describe your first thoughts on how to solve this problem. \nThe Intuition is to count all possible routes from a start city to a finish city, given
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe Intuition is to count all possible routes from a start city to a finish city, given a certain amount of fuel. It uses a recursive approach with memoization to optimize the computation.\n\nThe solve function performs the main computation. It checks if the remaining fuel is sufficient for each possible move and recursively explores all valid paths. The results of subproblems are stored in a memoization table to avoid redundant computations.\n\nBy using memoization, the code avoids recomputing the same routes multiple times, significantly improving efficiency. The approach enables the algorithm to handle larger inputs by reusing previously computed results, reducing the overall time complexity.\nhttps://youtu.be/ynTefMSqxjI\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity \n- Time complexity: O(N^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(Fuel*N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int mod = 1e9+7;\n    int solve(vector<int>& locations, int start, int finish, int fuel, vector<vector<int>>& dp)\n    {\n        //Base case\n        if(fuel< 0) return 0;\n        if(dp[start][fuel]!=-1) return dp[start][fuel];\n        int ans = 0;\n        if(start==finish) ans++;\n        for(int i =0;i<locations.size();i++)\n        {\n            if(i!=start && fuel >= abs( locations[i] - locations[start]))\n            {\n                ans = (ans + solve(locations, i, finish, fuel - abs(locations[i] - locations[start]),dp))%mod;\n            }\n        }\n        return dp[start][fuel] = ans;\n    }\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        int n = locations.size();\n        vector<vector<int>> dp(n+1, vector<int>(fuel+1, -1));\n        return solve(locations, start, finish, fuel,dp);\n    }\n};\n```\n![d691ebb2-63ce-470b-92ab-474a955c3392_1676870623.1558764.jpeg](https://assets.leetcode.com/users/images/cca3cfea-9c8f-4b71-b7cc-2447ad897f19_1687711953.5999265.jpeg)\n\n\n
['Array', 'Dynamic Programming', 'Memoization', 'C++']