2 ways Dynamic Programming || Simple for Beginners✅✅
Python3 []\nclass Solution:\n    def countRoutes(self, locations: List[int], start: int, finish: int, total_fuel: int) -> int:\n        @lru_cache(None)\n      
```Python3 []\nclass Solution:\n    def countRoutes(self, locations: List[int], start: int, finish: int, total_fuel: int) -> int:\n        @lru_cache(None)\n        def dfs(curr, fuel_left):\n            ways = 1 if curr == finish else 0\n            for i in range (len(locations)):\n                fuel = fuel_left - abs(locations[i] - locations[curr])\n                if fuel >= 0 and i != curr:\n                    ways = (ways + dfs(i, fuel)) % (10**9+7)\n            return ways\n        return dfs(start, total_fuel)\n```\n```python []\nclass Solution(object):\n    def countRoutes(self, locations, start, finish, total_fuel):\n        dp = {}; mod = 10**9+7\n        def dfs(curr, fuel_left):\n            if (curr, fuel_left) in dp:\n                return dp[curr, fuel_left]\n\n            ways = 0\n            if curr == finish:\n                ways = 1\n\n            for i in range (len(locations)):\n                fuel = fuel_left - abs(locations[i] - locations[curr])\n                if fuel >= 0 and i != curr:\n                    ways = (ways + dfs(i, fuel)) % mod\n                    \n            dp[(curr, fuel_left)] = ways\n            return ways\n\n        return dfs(start, total_fuel)\n```\n\n`@lru_cache(None)` actually caches each value of the tuple (curr, fuel_left) and stores it, if any value is passed with the same tuple values, it just returns the cached answer and does not call the function.\n\nHope it Helps. ^_^\n\n![image.png](https://assets.leetcode.com/users/images/af6e93b4-e706-42f3-87be-09c1c68f7e1a_1687686048.2147465.png)\n
['Dynamic Programming', 'Python', 'Python3']