Frog Jump

蛙跳问题, 一般的跳数问题都是贪婪算法. 但是这个问题比较特殊, 他给的是一个排序好的递增数组,表示石头的编号, 然后青蛙可以跳k, k-1, k+1三个固定的数字, 并且青蛙只能前跳. 那么这个问题可以直接用memo+dfs来做, 用一个map充当memo, 然后只需要每次查找上面三个位置是否有石头可以跳即可.

public class Solution {
    public boolean canCross(int[] stones) {
        return canCross(stones, 0 ,0);    
    }
    Map<Integer, Boolean> map = new HashMap<>(); //<stone|k, canJump?>
    public boolean canCross(int[] stones, int k, int pos) {
        int key = pos | k << 11; //compress the key
        if(map.containsKey(key))
            return map.get(key);
        for(int i = pos + 1; i < stones.length; i++) {
            int gap = stones[i] - stones[pos]; //find the gap
            if(gap < k - 1){
                map.put(key, false); // cannot jump
            }
            else if(gap > k + 1){
                map.put(key, false);
                return map.get(key);
            }
            else if(canCross(stones, gap, i)){
                map.put(key, true);
                return map.get(key);
            }
            
        }
        map.put(key, pos == (stones.length - 1)); // test if it is the last tone.
        return map.get(key);
    }
    
    
}