Dynamic Programming | Simple Explanation
Start from the start index, and visit all cities except start.\n2. Continue this process recursively.\n3. If you reach end index, do:\n    - Now, we have atleas
1. Start from the `start` index, and visit all cities except `start`.\n2. Continue this process recursively.\n3. If you reach `end` index, do:\n    - Now, we have atleast 1 way of reaching `end` so add this 1 possible way to the answer.\n    - Continue recursion, since there might be more ways to get back from `end` to `end` using other cities.\n4. If fuel < 0, there is no further way left.\n\nIf you look at this recursion, we can see that there are overlapping subproblems. If you reach a city `c` with fuel `f` multiple times from different paths, don\'t recompute, just use memoised result. \n\n```\nclass Solution {\n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        int n = locations.length;\n        long[][] dp = new long[n][fuel + 1];\n        for (int i = 0; i < n; ++i) {\n            Arrays.fill(dp[i], -1);\n        }\n        return (int) solve(locations, start, finish, dp, fuel);\n    }\n\t// dp[curCity][fuel] = number of ways to reach finish, when we are at city `curCity` with fuel `fuel`\n    private long solve(int[] locations, int curCity, int e, long[][] dp, int fuel) {\n        // 4. There is no further way left.\n        if (fuel < 0) return 0;\n        if (dp[curCity][fuel] != -1) return dp[curCity][fuel];\n        // 3. Now, if we have atleast 1 way of reaching `end`, add 1 to the answer. But don\'t stop right here, keep going, there might be more ways :)\n        long ans = (curCity == e) ? 1 : 0;\n        for (int nextCity = 0; nextCity < locations.length; ++nextCity) {\n            // 1. Visit all cities except `curCity`.\n            if (nextCity != curCity) {\n                // 2. Continue this process recursively.\n                ans = (ans + solve(locations, nextCity, e, dp, fuel - Math.abs(locations[curCity] - locations[nextCity]))) % 1000000007;\n            }\n        }\n        return dp[curCity][fuel] = ans;\n    }\n}\n```\n\nComplexity: `O(fuel*n^2)`
[]