The recursive is easy, but I am getting TLE and MLE on memoization.
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?