有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。

跳蚤跳跃的规则如下：

它可以 往前 跳恰好 a 个位置（即往右跳）。
它可以 往后 跳恰好 b 个位置（即往左跳）。
它不能 连续 往后跳 2 次。
它不能跳到任何 forbidden 数组中的位置。
跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。

给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，
同时给你整数 a， b 和 x ，
请你返回跳蚤到家的最少跳跃次数。
如果没有恰好到达 x 的可行方案，请你返回 -1 。

class Solution {
	
	int MAX_INT =(1<<31) -1;
	int ans = MAX_INT;
	
	HashMap<String, Integer> map;

    public int minimumJumps(int[] forbidden, int a, int b, int x) {
		
		HashSet<Integer> set = new HashSet<>();
		for(int tmp: forbidden){
			set.add(tmp);
		}
		int[] tot = new int[]{0};
		map = new HashMap<>();
		dfs(set, a, b, x, 0, 0, tot);
		return ans==MAX_INT?-1: ans;
    }
	
	/*
		cur：当前位置
		type: 0表示向左或向右都可以，1表示只能向右
		tot：存储从0到cur的跳跃次数
		
		返回值：从cur 到达x的最小跳跃次数
	*/
	public int dfs(HashSet<Integer> set, int a, int b, int x, int cur, int type, int[] tot){
	
		// 记忆化的key
		String key = String.format("%s-%s", cur, type);
	
		// 如果b<=a 且x>cur+b，就永远跳不到x了，直接返回
		if(x>cur+b && b<=a){
			map.put(key, -1);
			return -1;
		}
		
		// 剪枝：如果当前累计的 >= 目前已知的最优解，跳过
		if(tot[0] >= ans){
			map.put(key, -1);
			return -1;
		}
		
		if(cur==x){
			ans = Math.min(ans, tot[0]);
			return 0;
		}
		
		if(map.containsKey(key))
			return map.get(key);
		
		int[][] nxts = new int[][]{};
		if(type==0){
			nxts = new int[][]{
				new int[]{cur-b, 1},
				new int[]{cur+a, 0}
				
			};
		}else{
			nxts = new int[][]{
				new int[]{cur+a, 0}
			};
		}
		
		int minSteps = MAX_INT;
		for(int[] nxt: nxts){
			int cur0 = nxt[0];
			int type0 = nxt[1];
			if(cur0<0 || set.contains(cur0))
				continue;
			++ tot[0];
			int steps = dfs(set, a, b, x, cur0, type0, tot);
			-- tot[0];
			
			if(steps!=-1){
				minSteps = Math.min(minSteps, 1+steps);
			}
		}
		
		if(minSteps==MAX_INT){
			map.put(key, -1);
			return -1;
		}else{
			map.put(key, minSteps);
			return minSteps;
		}
	}
}