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);
}
}