DP + Video Solution | Java C++ Python
Intuition\nStarting from the current city, we explore all possible cities we can reach with the remaining fuel. For each reachable city, we recursively call the
# Intuition\nStarting from the current city, we explore all possible cities we can reach with the remaining fuel. For each reachable city, we recursively call the function, updating the current city, remaining fuel, and accumulating the number of valid routes.\n\nThe memoization technique ensures that we store the results of subproblems, so if we encounter the same subproblem again, we can directly retrieve the result from memory instead of recomputing it.\n\n<iframe width="560" height="315" src="https://www.youtube.com/embed/GPoCSI5DZMk" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>\n\n```\nclass Solution {\n    int [][] dp;\n    int n;\n    int finish;\n    public int solve(int[] locations, int currCity, int remainingFuel) {\n        if (remainingFuel < 0) {\n            return 0;\n        }\n        if (dp[currCity][remainingFuel] != -1) {\n            return dp[currCity][remainingFuel];\n        }\n\n        int ans = currCity == finish ? 1 : 0;\n        for (int nextCity = 0; nextCity < n; nextCity++) {\n            if (nextCity != currCity) {\n                ans = (ans + solve(locations, nextCity,\n                remainingFuel - Math.abs(locations[currCity] - locations[nextCity]))) % 1000000007;\n            }\n        }\n\n        return dp[currCity][remainingFuel] = ans;\n    }\n\n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        n = locations.length;\n        dp = new int[n][fuel + 1];\n        this.finish = finish;\n        for (int i = 0; i < n; ++i) {\n            Arrays.fill(dp[i], -1);\n        }\n\n        return solve(locations, start, fuel);\n    }\n}\n```\n\n```\nclass Solution {\n    vector<vector<int>> dp;\n    int n;\n    int finish;\n\n    int solve(vector<int>& locations, int currCity, int remainingFuel) {\n        if (remainingFuel < 0) {\n            return 0;\n        }\n        if (dp[currCity][remainingFuel] != -1) {\n            return dp[currCity][remainingFuel];\n        }\n\n        int ans = (currCity == finish) ? 1 : 0;\n        for (int nextCity = 0; nextCity < n; nextCity++) {\n            if (nextCity != currCity) {\n                ans = (ans + solve(locations, nextCity,\n                    remainingFuel - abs(locations[currCity] - locations[nextCity]))) % 1000000007;\n            }\n        }\n\n        return dp[currCity][remainingFuel] = ans;\n    }\n\npublic:\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        n = locations.size();\n        dp.resize(n, vector<int>(fuel + 1, -1));\n        this->finish = finish;\n\n        return solve(locations, start, fuel);\n    }\n};\n```\n```\nclass Solution:\n    def solve(self, locations, currCity, remainingFuel):\n        if remainingFuel < 0:\n            return 0\n        if self.dp[currCity][remainingFuel] != -1:\n            return self.dp[currCity][remainingFuel]\n\n        ans = 1 if currCity == self.finish else 0\n        for nextCity in range(self.n):\n            if nextCity != currCity:\n                ans = (ans + self.solve(locations, nextCity,\n                        remainingFuel - abs(locations[currCity] - locations[nextCity]))) % 1000000007\n\n        self.dp[currCity][remainingFuel] = ans\n        return ans\n\n    def countRoutes(self, locations, start, finish, fuel):\n        self.n = len(locations)\n        self.dp = [[-1] * (fuel + 1) for _ in range(self.n)]\n        self.finish = finish\n\n        return self.solve(locations, start, fuel)\n\n```
['C', 'Python', 'Java']