Clear Explanation with Easy Recursive DFS Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nTry all paths from the start until you run out of fuel. From all the possible paths, ke
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTry all paths from the start until you run out of fuel. From all the possible paths, keep a count of which paths end on the finishing location from the start. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThere are two insights which make this problem relatively easy to solve. First, note that you aren\'t allowed to travel to the same location which you are one. If this was allowed, then there would be an infinite number of routes since there is no fuel used to travel to the same path. Second, each time you visit a location, there is a different level of fuel left in the tank. If we consider the location and fuel as a tuple, then this acts as a node in a graph. Our task is to find all paths which start from the node (start, fuel) \u2014 where start is the staring location and fuel is the starting fuel \u2014 to (finish, endFuel) where $endFuel \\ge 0$. \n\nThinking of the possible states as a graph allows us to apply a graph traversal algorithm like depth-first search from the starting node (start, fuel).\n\nOn a high level, the algorithm works by exploring all other locations from a given node (index, fuel). If the current index is the finish location, then we can increment our routes count by 1. However, before we do this, we need to check if we have enough fuel left for this path to be considered valid. Next, from this current location, we try to extend the path by exploring all other locations in the locations array and adjusting the amount of fuel we have left. In the end, we return the route count modulo $10^9 + 7$. Since we are going to be making a lot of recursive calls, and the possibility that we are allowed to visit a location multiple times, we cache the route from from (index, fuel) in a dictionary for constant lookup. \n\nFirst, we initialize a cache. The cache is a dictionary where the keys are tuples of (index, fuel) \u2014 the current location and the current fuel \u2014 and the values are the number of valid routes from this state to the finish. Next, for our main ```countRoutes``` method, with first store the modulus for convenience. Next, we call a private recursive method ```_travel```, which takes in all arguments passed to ```countRoutes```. This method will return the number of valid routes from start to finish with the starting fuel. Finally, we return this count after taking the mod value. Now, all we have to do is implement the ```_travel``` method. \n\nThe ```_travel``` method is fairly straightforward. We first initialize a variable ```total``` which stores the number of valid routes. We then check if we have enough fuel left. We can arrive at a location with no fuel left but if we have negative fuel, then this means that the current path being considered is invalid and we can return 0. We then check if the current state is stored in the cache. If it is, then we return the its value from the cache. If not, then we check if the current location is the finish, in which case we have found a valid route and therefore we increment our total count by 1. \n\nNow, to explore all other locations, we iterate over the locations. We need to decrease the fuel by the amount it costs to get to the next location. We then increment total by all the valid routes from the nextLocation. \n\nIn the end, we store the current route count in our cache, and return the total. \n\nNote that I am presenting a solution where we are manually caching the results. In python, we can use the ```@lru_cache(None)``` decorator which will take care of this automatically but this approach provides a deeper understanding. \n\n# Complexity\n- Time complexity: $O(n^2 \\cdot f)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$O(n \\cdot f)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def __init__(self) -> None:\n        """\n        Initialize a cache which will store the number of paths which include a \n        particular location with a particular amount of fuel\n        """\n\n        self.cache = {} # key: (location, fuel), val : routes\n\n    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n        """\n        Returns the number of routes possible from start location to the finish location\n        with a particular amount of fuel\n\n        Args:\n            locations: List[int] = fuel costs for travelling between locations which are the indices\n            start: int = starting location represented by an index\n            finish: int = finishing location represented by an index\n            fuel: int = amount of fuel at the start of the journey\n        \n        Returns:\n            routes: int = number of possible routes\n        """\n        \n        # Store the modulus in a variable for convenience\n        mod = 10 ** 9 + 7\n\n        # Calculate the number of routes from start to finish with starting fuel\n        routes = self._travel(locations, start, finish, fuel)\n\n        # Return the number of routes module 10**9 + 7\n        return routes % mod\n\n    def _travel(self, locations: List[int], index: int, finish: int, fuel: int) -> int:\n        """\n        Returns the number of routes possible from start location to the finish location\n        with a particular amount of fuel\n\n        Args:\n            locations: List[int] = fuel costs for travelling between locations which are the indices\n            start: int = starting location represented by an index\n            finish: int = finishing location represented by an index\n            fuel: int = amount of fuel at the start of the journey\n        \n        Returns:\n            total: int = number of possible routes\n        """\n\n        # Initialize the total number of routes \n        total = 0\n\n        # If we are out of fuel, then this current route is invalid and therefore\n        # can\'t be considered in our total\n        if fuel < 0:\n            return 0\n\n        # if we have already been to this current location with the current fuel level,\n        # then we don\'t need to recalulate the number of valid paths from this state since\n        # we have stored that result in our cache and we can return that\n        if (index, fuel) in self.cache:\n            return self.cache[(index, fuel)]\n        \n        # If we have a valid amount of fuel and are currently at the finishing point, \n        # this route is valid. However, since we can revisit some other locations, we\n        # just increment our total route count and continue visiting the other locations\n        if index == finish:\n            total += 1\n\n        # Storing the current locations fuel cost for convenience\n        currentCost = locations[index]\n\n        # Iterate over the other locations in the array while keeping track of that location\'s\n        # fuel cost\n        for nextStop, cost in enumerate(locations):\n            # We only explore locations different than the current locationn\n            if nextStop != index:\n                # We subtract the fuel used to get to the next location\n                fuelLeft = fuel - abs(cost - currentCost)\n                # We increment total to include all paths which lead to the finish \n                # from the next location\n                total += self._travel(locations, nextStop, finish, fuelLeft)\n        \n        # We store the number of routes for this state in case it is needed later\n        # and return the total number of routes\n        self.cache[(index, fuel)] = total \n        return total\n\n    \n```
['Depth-First Search', 'Memoization', 'Python3']