403. Frog Jump

T: O(n^2), pos , jump 需要存储的状态是{pos, jump}，这些状态可能都会被走到，所以时间复杂度是n^2.

S: O(n^2)

class Solution {
    public boolean canCross(int[] stones) {
        Set<Integer> stoneSet = new HashSet();
        for (int s : stones) {
            stoneSet.add(s);
        }
        
        //int last = stones[stones.length-1];
        Set<String> failedMemo = new HashSet();
        return dfs(stones, 0, 0, failedMemo, stoneSet);
    }
    private boolean dfs(int[] stones, int pos, int jump, Set<String> failedMemo, Set<Integer> stoneSet) {
        if (stones[stones.length-1] == pos) {
            return true;
        }
        if (!stoneSet.contains(pos)) {
            return false;
        }
        if (failedMemo.contains(pos + "," + jump)) {
            return false;
        }
        
        if (jump > 1 && dfs(stones, pos+jump-1, jump-1, failedMemo, stoneSet)) {
            return true;
        }
        if (jump > 0 && dfs(stones, pos+jump, jump, failedMemo, stoneSet)) {
            return true;
        }
        if (dfs(stones, pos+jump+1, jump+1, failedMemo, stoneSet)) {
            return true;
        }
        
        failedMemo.add(pos + "," + jump);
        return false;
    }
}
/*
 The frog can jump on a stone, but it must not jump into the water.
 
 asc
 
dfs(stones, pos, jump, memo)

if (pos == last stone)
if (!stones.contains(pos) true
if (memo[failed]) false

dfs(jump > 1pos+jump-1, jump-1)

dfs(jump > 0 pos+jump, jump)

dfs(pos+jump+1, jump+1)


memo[failed][][] =
return false;
*/