C++ ✅ | 2D DP 🌟 | Easy Solution
Approach\n\n###### We only stop when fuel becomes empty, You might have the question for the base condition when cur position is finish. But if we are at finish
# Approach\n\n###### We only stop when fuel becomes empty, You might have the question for the base condition when cur position is finish. But if we are at finish point and we still have fuel which can go over some location and return back to finish. This should be counted here. And that\'s the reason not to write base case of `if (idx == finish) return 1;`\n\n###### For more understanding, see the code below.\n\n# Complexity\n- Time complexity: $$O(n * 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# Code\n```\nclass Solution {\npublic:\n    long dp[101][201], mod = 1e9 + 7;\n    long solve(int idx, int fuel, int &finish, vector<int> &locations)\n    {\n        if (fuel < 0)\n            return 0;\n\n        if (dp[idx][fuel] != -1)\n            return dp[idx][fuel];\n\n        long ans = 0;\n\n        for (int i = 0; i < locations.size(); i++)\n            if (i != idx)\n                ans = (ans + solve(i, fuel - abs(locations[idx] - locations[i]), finish, locations)) % mod;\n\n        return dp[idx][fuel] = (idx == finish) + ans;\n    }\n    int countRoutes(vector<int> &locations, int start, int finish, int fuel)\n    {\n        memset(dp, -1, sizeof(dp));\n        return solve(start, fuel, finish, locations);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']