I have been trying to implement the recursive solution for the [Leetcode Minimum Number of Refueling Stops][1]. I came up with the solution below but it doesn't pass all test cases. I have put so much effort into this. I would appreciate a support. Here is my code so far:

    static int startTarget;
    private static int helper(int target, int currentFuel, int start, int[][] stations, Map<String, Integer> memo) {
        if (stations.length == 0)
            return currentFuel < target ? -1 : 0;

        if (stations[0][0] > currentFuel)
            return -1;

        String key = target   ", "   currentFuel;
        if (memo.containsKey(key))
            return memo.get(key);

        if (currentFuel >= target)
            return 0;

        if (start == stations.length)
            return -1;

        int min = Integer.MAX_VALUE;
        for (int i = start; i < stations.length; i  ) {
            int currentDistance = stations[i][0];
            int initialDistance = startTarget - target;
            int distance = currentDistance - initialDistance;
            int fuel = stations[i][1];

            if ((currentFuel - distance) >= 0) {
                int result = helper(target - distance, currentFuel   fuel - distance, i   1, stations, memo);
                if (result >= 0 && result < min)
                    min = 1   result;
            }

        }
        min = (min == Integer.MAX_VALUE) ? -1 : min;
        memo.put(key, min);
        return min;
    }

    public static  int minRefuelStopsBruteForce(int target, int startFuel, int[][] stations) {
        startTarget = target;
        int stops = helper(target, startFuel, 0, stations, new HashMap<>());
        return stops != Integer.MAX_VALUE ? stops : -1;
    }

Please I am only interested in the recursive solution.Thanks [1]: https://leetcode.com/problems/minimum-number-of-refueling-stops/

CodePudding user response：

You are pretty close but there are some errors. For example, it does not make sense to check station[0][0] all the time (second if statement). And the HashMap should not be needed.

I wrote a solution that I think works, but I'm not sure you want it. I think you can solve this on your own, which is a lot more awarding. I suggest you start from scratch, and give it another try. Here are a few hints:

I think you can take these if statements away:

if (stations.length == 0)...
if (stations[0][0] > currentFuel)...
if (memo.containsKey(key))...

I think it is easier to follow the code if you don't change "target" (currently you subtract distance). Instead, add a parameter that tells "helper" how far you have travelled (distance).

Give it another try, I'm sure you'll make it. If not, let me know, and I'll post my code :)

CodePudding user response：

Information wants to be free, so here you go :)

This solution uses the same approach as your solution, and it seems to work, so you can look at it to see what needs to be fixed with your code.

Sadly it is way to slow, so execution stops with "Time limit exceeded" at test case #115 that has approx 100 gas stations. So to solve the Leetcode task with recursion, a whole new way of thinking is needed.

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    Integer result = helper(-1, startFuel, target, stations, 0);
    return result == null ? -1 : result.intValue();
}

private Integer helper(int currentStation, int currentFuel, int target, int[][] stations, int depth) {
    int currentPos = currentStation == -1 ? 0 : stations[currentStation][0];
    if (currentPos   currentFuel >= target) {
        return 0;
    }

    Integer best = null;
    for (int i = currentStation   1; i < stations.length; i  ) {
        int stationPos = stations[i][0];
        int stationFuel = stations[i][1];
        // Check out station that we have not yet passed && we can reach
        if (currentPos < stationPos && currentPos   currentFuel >= stationPos) {
            // Drive to station
            int fuel = currentFuel - (stationPos - currentPos);
            // Fill up gas
            fuel  = stationFuel;
            // Continue
            Integer res = helper(i, fuel, target, stations, depth   1);
            if (res != null && (best == null || res < best)) {
                best = res;
            }
        }
    }

    // Return "no can do" or return number of stations (adding *this* station)
    return best == null ? null : best   1;
}