easy C++/Python dfs  DP solutions
Intuition\n Describe your first thoughts on how to solve this problem. \nUse DFS and DP. Set dp[i][fuel] as the state for the city i and with fuel=fuel.\n# Appr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse DFS and DP. Set dp[i][fuel] as the state for the city i and with fuel=fuel.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe given code counts the number of routes from a start to a finish location within a fuel limit. It uses dynamic programming with a recursive function. The code initializes a 2D list to store route counts. The dfs function recursively explores routes, incrementing the count for valid routes. It memoizes the counts to avoid redundant calculations. The function returns the count of routes from start to finish with the given fuel. The code improves efficiency by reusing intermediate results, enhancing performance compared to naive recursive approaches.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(n^2 * fuel)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(n * fuel)$\n# Code\n\n```C++ []\nclass Solution {\npublic:\n    const int Mod=1e9+7;\n    \n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        int n=locations.size();\n        vector<vector<int>> dp(n, vector(fuel+1, -1));\n\n        function<int(int, int, int)> dfs=[&](int i, int finish, int fuel)->int{\n            if (fuel<0) return 0;\n            if (dp[i][fuel]!=-1) return dp[i][fuel];\n            int ans=0;\n            if (i==finish) ans++;\n            for(int j=0; j<n; j++){\n                if (j==i) continue;\n                ans=(ans+dfs(j, finish, fuel-abs(locations[i]-locations[j])))%Mod;\n            }\n            return  dp[i][fuel]=ans;\n        };\n\n        return dfs(start, finish, fuel);\n    }\n};\n```\n```python []\nclass Solution:\n    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n        Mod=10**9+7\n        n=len(locations)\n        row=[-1]*(fuel+1)\n        dp=[row[:] for _ in range(n)]\n\n        def dfs(i, finish, fuel):\n            if fuel<0: return 0\n            if dp[i][fuel]!=-1: return dp[i][fuel]\n            ans=0\n            if i==finish: ans+=1\n            for j in range(n):\n                if j==i: continue\n                ans=(ans+dfs(j, finish, fuel-abs(locations[i]-locations[j])))%Mod\n            dp[i][fuel]=ans\n            return ans\n\n        return dfs(start, finish, fuel)\n```\n
['Dynamic Programming', 'Depth-First Search', 'Recursion', 'C++', 'Python3']