aakarshmadhavan's blog

By aakarshmadhavan, history, 6 years ago, In English

The recursive is easy, but I am getting TLE and MLE on memoization.

Problem

class Solution {
    int N;
    int [][] stations;
    Map<Integer, Integer> map = new HashMap<>();
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        this.N = stations.length;
        this.stations = stations;
        for(int i = 0; i < stations.length; ++i){
            int [] s = stations[i];
            map.put(s[0], i);
        }
        map.put(0, -1);
        int sol = helper(0, startFuel, target);
        return (sol >= N + 1) ? -1 : sol;
    }
    
    public int helper(int station, int fuel, int target){
        if(station + fuel >= target) return 0;
        if(fuel <= 0) return N + 1;
        int cur = N + 1;
        for(int i = map.get(station) + 1; i < stations.length; ++i){
            int [] current = stations[i];
            if(fuel - (current[0] - station) < 0) continue;
            cur = Math.min(cur, 1 + helper(current[0], fuel - (current[0] - station) + current[1], target));
        }
        
        return cur;
    }
}

But I use 2D Array for memoization, it doesn't work because the array will be too big and also time complexity is bad.

Can someone help me?

  • Vote: I like it
  • -16
  • Vote: I do not like it