Frog Jump
蛙跳问题, 一般的跳数问题都是贪婪算法. 但是这个问题比较特殊, 他给的是一个排序好的递增数组,表示石头的编号, 然后青蛙可以跳k, k-1, k+1三个固定的数字, 并且青蛙只能前跳. 那么这个问题可以直接用memo+dfs来做, 用一个map充当memo, 然后只需要每次查找上面三个位置是否有石头可以跳即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
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); } } |