Help me memoize

Revision en1, by aakarshmadhavan, 2018-07-15 09:44:01

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English aakarshmadhavan 2018-07-15 09:44:01 1359 Initial revision (published)