How to come up with the Recursive solution for Leetcode Minimum Number of Refueling Stops

Question

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/

Answer 1

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;
}