【leetcode】403 Frog Jump

发表于

一只青蛙正在过河。 河流分为x个单位，每个单位可能存在或不存在石头。青蛙可以跳到石头上，
但不能跳入水中。



描述
一只青蛙正在过河。 河流分为x个单位，每个单位可能存在或不存在石头。 青蛙可以跳到石头上，但不能跳入水中。

给出按照升序排序的石块位置（单位），确定青蛙是否能够通过落在最后一块石头上过河。 最初，青蛙在第一块石头上并假设第一次跳跃必须是1个单位。

如果青蛙的最后一次跳跃是k个单位，那么它的下一个跳跃必须是k-1，k或k + 1个单位。 请注意，青蛙只能向前跳。

样例1

1
2
输入: [0,1,3,5,6,8,12,17]
输出: true

样例2

1
2
输入: [0,1,2,3,4,8,9,11]
输出: false

解题思路
本题就难在稍大规模的数据，不剪枝的话耗时很长。剪枝思路是，当上一步步长过大，下一个有石头的地方太近，则直接跳过下一个石头，转到下下个石头。当上一步步长过小，无法到达下一个有石头的地方，则直接返回false。

下面代码中左移30位的作用是保证每一种方案的唯一性，记忆搜索。另外，创建不知道个数的dp可以采用map来保存。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    unordered_map <int,bool> dp;

    bool canCross(vector<int>& stones) {
        dp = {};
        return recursive(stones,0, 0);
    }

    bool recursive(vector<int>& stones, int index, int step) {
        int key = index << 30 | step;
        if (dp.find(key) != dp.end()) { return dp[key]; }
        for (int i = index + 1; i < stones.size(); i++) {
            int gap = stones[i] - stones[index];
            if (gap < step - 1) { continue; }
            if (gap > step + 1) { return dp[key] = false; }
            if (recursive(stones, i, gap)) { return dp[key] = true; }
        }
        return index+1 == stones.size();
    }
};

参考资料
原题链接