From recursion🧑‍💻🧑‍💻 to memoization 🚀🚀
Intuition\nTheir is simple intution that try to form the adjacency matrix and try to trverse through recursion.\nNow we optimise using memoization.\n Describe y
# Intuition\nTheir is simple intution that try to form the adjacency matrix and try to trverse through recursion.\nNow we optimise using memoization.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe approach used in the provided code can be outlined as follows:\n\n1. Initialize a counter variable `cnt` to keep track of the count of valid routes.\n2. Define a recursive function `dfs` that takes the current position `in`, the finish position `finish`, the remaining fuel `fuel`, the array of locations `locations`, the adjacency list `adj`, and a memoization table `memo`.\n3. Inside the `dfs` function, check if the remaining fuel `fuel` is negative. If it is, return 0 since no more routes are possible with negative fuel.\n4. Check if the current position `in` is the finish position `finish`. If it is, set `cnt` to 1 since a valid route has been found.\n5. If the memoization table `memo` already has a value for the current position `in` and remaining fuel `fuel`, return the memoized result.\n6. Iterate through the neighbors of the current position `in` in the adjacency list `adj`.\n7. Calculate the distance `dist` between the current position `in` and its neighbor `it` using the locations array `locations`.\n8. Check if the remaining fuel `fuel` is greater than or equal to the distance `dist`. If it is, recursively call the `dfs` function for the neighbor `it` with updated parameters: new position `it`, updated fuel `fuel - dist`, and the same values for `finish`, `locations`, `adj`, and `memo`. Add the result of the recursive call to `cnt`.\n9. Memoize the result `cnt` for the current position `in` and remaining fuel `fuel` in the memoization table `memo`.\n10. Return the memoized result `cnt` as the count of valid routes from the current position `in` with the given fuel `fuel`.\n11. In the `countRoutes` function, initialize the adjacency list `adj` based on the locations array `locations`.\n12. Initialize the memoization table `memo` with appropriate dimensions.\n13. Call the `dfs` function with the starting position `start`, finish position `finish`, initial fuel `fuel`, `locations`, `adj`, and `memo`.\n14. Return the result obtained from the `dfs` function as the count of valid routes.\n\nThis approach utilizes recursion and memoization to efficiently count the number of valid routes. By avoiding redundant computations through memoization, the overall time complexity is reduced.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:$$O(n^2+n*fuel)$$ \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n*fuel)$$ \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Not Optimised Using recursion\n```\nclass Solution {\npublic:\nint cnt=0;\n   void dfs(int in,int finish,int fuel,vector<int>& locations,vector<int>adj[]){\n       if(in==finish){\n                cnt++;\n              for(auto it:adj[finish]){\n                  int dist = abs(locations[in] - locations[it]);\n                    if (fuel >= dist) {\n           dfs(it,finish,fuel-abs(locations[it]-locations[in]),locations,adj);\n              } \n              }  \n           return;\n       }\n       for(auto it:adj[in]){\n             int dist = abs(locations[in] - locations[it]);\n                    if (fuel >= dist) {\n           dfs(it,finish,fuel-abs(locations[it]-locations[in]),locations,adj);\n   }\n       }\n   }\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        int n=locations.size();\n\n        vector<int>adj[n+1];\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                 if(i!=j){\n                  adj[i].push_back(j);\n                 }\n            }\n        }\n        dfs(start,finish,fuel,locations,adj);\n        return cnt;\n    }\n};\n```\nNow we make use of dp to optimise it\n# Code\n```\nclass Solution {\npublic:\n    int dfs(int in, int finish, int fuel, vector<int>& locations, vector<int> adj[], vector<vector<int>>& memo) {\n        if (fuel < 0) {\n            return 0; // No more routes possible with negative fuel\n        }\n int cnt = 0;\n        if (in == finish ) {\n           cnt=1; // Reached the destination with positive fuel, one valid route found\n        }else{\n            cnt=0;\n        }\n\n        if (memo[in][fuel] != -1) {\n            return memo[in][fuel]; // Return memoized result if available\n        }\n\n       \n        for (int it : adj[in]) {\n            int dist = abs(locations[in] - locations[it]);\n            if (fuel >= dist) {\n                cnt = (cnt + dfs(it, finish, fuel - dist, locations, adj, memo)) % 1000000007;\n            }\n        }\n\n        return memo[in][fuel] = cnt; // Memoize and return the count\n    }\n\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        int n = locations.size();\n\n        vector<int> adj[n];\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (i != j) {\n                    adj[i].push_back(j);\n                }\n            }\n        }\n\n        vector<vector<int>> memo(n, vector<int>(fuel + 1, -1)); // Memoization table\n        return dfs(start, finish, fuel, locations, adj, memo);\n    }\n};\n\n```\n
['Recursion', 'Memoization', 'C++']