Easy Java Solution | DP
\n# Code\n\nclass Solution {\n    \n    int MOD = (int)1e9 + 7;\n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n\n        int l
\n# Code\n```\nclass Solution {\n    \n    int MOD = (int)1e9 + 7;\n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n\n        int l = locations.length;\n        int[][] dp = new int[l + 1][fuel + 1];\n        for(int[] num : dp){\n            Arrays.fill(num, -1);\n        } \n        return helper(locations, start, finish, fuel, dp);\n    }\n\n    private int helper(int[] locations, int start, int finish, int fuel, int[][] dp) {\n        int result = 0;\n        \n        if(fuel < 0) return result;\n        \n        if(dp[start][fuel] != -1) return dp[start][fuel];\n        \n        // If the start and finish are the same, increment the result\n        if(start == finish) result++;\n        \n        for(int i = 0; i < locations.length; i++) {\n            if(i == start) continue; // Skip the current city if it is the same as the start city\n            \n            int fuelConsumed = Math.abs(locations[start] - locations[i]);\n            \n            // Recursively calculate the count of routes from city i to the finish city\n            result += helper(locations, i, finish, fuel - fuelConsumed, dp);\n            result %= MOD;\n        }\n        // Store the result in the dp array \n        dp[start][fuel] = result;\n        return result;\n    }\n}\n\n```
['Dynamic Programming', 'Java']