🔥🔥C++ Solution || ✅✅ Memoization in Dynamic Programming🔥🔥
\n\n# Approach\n Describe your approach to solving the problem. \n1. Initialize a variable n to the size of the locations vector.\nCreate a memoization table dp
\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize a variable `n` to the size of the locations vector.\nCreate a memoization table `dp` as a 2D vector of size `n x (fuel + 1)` and initialize all elements to -1.\n\n2. In the base case,if the remaining fuel is negative (`remFuel < 0`), return 0, as it is not possible to reach the destination with negative fuel.\n\n3.  If the current location and remaining fuel combination has already been computed and stored in the memoization table (`dp[curr][remFuel] != -1`). If so, return the precomputed result to avoid redundant computations.\n4. Initialize a variable `res` to 0, which will store the count of valid routes.\nCheck if the current location is the same as the destination (`curr == finish`). If so, increment res by 1, as a valid route has been found.\n\n5. Store the computed result (`res`) in the memoization table at the current location and remaining fuel index (`dp[curr][remFuel]`) for future use.\n\n6. Return `res` as the final count of routes from the start location to the finish location within the given fuel limit.\n\n\n\n# Complexity\n- Time complexity: $$O(n^2.fuel)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: $$O(n.fuel)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\npublic:\n    int mod=1e9+7;\n\n    int solve(vector<int>& locations,int curr,int finish,int remFuel, vector<vector<int>> &dp){\n\n        //base case\n        if(remFuel<0){\n            return 0;\n        }\n\n        if(dp[curr][remFuel]!=-1){\n            return dp[curr][remFuel];\n        }\n\n        int res=curr==finish?1:0;\n\n        for(int i=0;i<locations.size();i++){\n            if(i!=curr){\n                res=(res+solve(locations,i,finish,remFuel-abs(locations[curr]-locations[i]),dp))%mod;\n            }\n        }\n\n        return dp[curr][remFuel]=res;\n\n    }\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        \n        int n=locations.size();\n\n        vector<vector<int>> dp(n,vector<int>(fuel+1,-1));\n\n        return solve(locations,start,finish,fuel,dp);\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']