/*朴素DP*/
public class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> stoneMap = new HashMap<>();
        for (int i=1;i<stones.length;i++) {
            stoneMap.put(stones[i], new HashSet<Integer>());
        }
        
        if (stones[0]+1 == stones[1]) {
            stoneMap.get(stones[1]).add(1);
        }
        
        for(int i=1;i<stones.length;i++) {
            int nowStone = stones[i];
            for(Integer k:stoneMap.get(nowStone)) {
                if (k != 1 && stoneMap.containsKey(nowStone + k - 1)) {
                    stoneMap.get(nowStone + k - 1).add(k - 1);
                }
                if(stoneMap.containsKey(nowStone + k)) {
                    stoneMap.get(nowStone + k).add(k);
                }
                if(stoneMap.containsKey(nowStone + k + 1)) {
                    stoneMap.get(nowStone + k + 1).add(k + 1);
                }
            }
        } 
        return stoneMap.get(stones[stones.length - 1]).size() >= 1;
    }
}

public class Main {
	public static void main(String args[]) {
		Solution s = new Solution();
		int[] stones = {0,1,2,3,4,8,9,11};
		System.out.println(s.canCross(stones));
	}
}