Help me memoize

Правка en1, от 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский aakarshmadhavan 2018-07-15 09:44:01 1359 Initial revision (published)