Dynamic Programming With Memoization
Start from each location\n2. If Fuel is less than 0 - return 0 (Since no path present)\n3. If Start is same as Finish - add 1 to our result (Since we can add th
1. Start from each location\n2. If Fuel is less than 0 - return 0 (Since no path present)\n3. If Start is same as Finish - add 1 to our result (Since we can add this to our result)\n4. Memoize in HashMap With `Start` and `remainign fuel` as Key\n5. NOTE : Return type to be kept as Long\n\n```\nclass Solution {\n    long MOD = 1000_000_007;\n    int[] locations;\n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        this.locations = locations;\n        return (int) countRoutesDp(start, finish, fuel, new HashMap<>());\n    }\n    \n    /// Use Return Type as Long - Since internal result may not fit Int limit before MOD \n    private long countRoutesDp(int start, int finish, int fuel, Map<String, Long> memo) {\n        if(fuel < 0) return 0;\n        long totalWays = 0;\n        //// Start is Same as Finish - Add 1 and then Continue further\n        if(start == finish) totalWays += 1; \n        /// Unique Key - Start And Remaining Fuel\n        String key = start + "#" + fuel;\n        if(memo.containsKey(key)) return memo.get(key);\n        \n        for(int nextLoc=0;nextLoc<locations.length;nextLoc++) {\n            /// Continue Since previous start was same has next location\n            if(nextLoc == start) continue;\n            /// required fuel for this Path\n            int reqFuel = Math.abs(locations[start] - locations[nextLoc]);\n            if(reqFuel <= fuel) { /// Continue to this (nextLoc) location only if sufficient fuel is available\n                totalWays += countRoutesDp(nextLoc, finish, fuel - reqFuel, memo) % MOD;\n            }\n        }\n        /// MOD the result before Returning\n        totalWays %= MOD;\n        memo.put(key, totalWays);\n        return totalWays;\n    }\n}
['Dynamic Programming', 'Memoization', 'Java']