题目描述

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。

开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

样例1

输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。

样例2

输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。

提示

• 2 <= stones.length <= 2000
• 0 <= stones[i] <= 2^31 - 1
• stones[0] == 0

算法1

(DFS) TLE

• 如何设计dfs函数：考虑如何跳到第i块石头以及每一步的状态，我们需要枚举每次跳到哪一块石头，以及上一步跳跃了多远
• 初始状态为从下标0开始跳跃，前一步跳跃距离为0
• 枚举每种可能的跳跃距离，并且判断新的跳跃位置在数组中是否存在，为了快速判断一个数是否存在，用哈希表存储数组中所有的数以及对应的下标；如果能跳跃到下一个位置，则更新下一个位置的下标以及跳跃距离

• 退出条件：如果能搜索到数组的最后一个位置，即能跳跃到重点，则返回true

• 时间复杂度：$O(3^n)$，每一次跳跃都有三种情况，最多跳跃n次

Java 代码

class Solution {
    Map<Integer,Integer> map = new HashMap<>();
    int n;
    public boolean canCross(int[] stones) {
        n = stones.length;
        for(int i = 0; i < n; i++){
            map.put(stones[i], i);
        }
        return dfs(stones, 0, 0);
    }

    // u为当前走到的位置下标
    // last为上一步跳了几个单位
    boolean dfs(int[] stones, int u, int last){
        if(u == n - 1) return true;
        for(int i = -1; i <= 1; i++){
            int cur = i + last;
            if(cur > 0){
                int next = stones[u] + cur;
                if(map.containsKey(next) && dfs(stones, map.get(next), cur)){
                    return true;
                }
            }
        }
        return false;
    }
}

算法2

(记忆化搜索)

• 考虑到dfs代码超时，对其进行改造：将dfs函数中的可变参数作为memo数组的维度，利用dfs函数的返回值对memo数组进行更新

• 由于数组最大长度为2000，下标i最远能跳i+1步，所以我们最大的跳跃距离为2000，数组范围开到2000以上即可

• 时间复杂度：$O(n^2)$

Java代码

• 用数组做标记

class Solution {
    Map<Integer,Integer> map = new HashMap<>();
    int n;
    Boolean[][] memo = new Boolean[2010][2010];
    public boolean canCross(int[] stones) {
        n = stones.length;
        for(int i = 0; i < n; i++){
            map.put(stones[i], i);
        }
        return dfs(stones, 0, 0);
    }

    // u为当前走到的位置下标
    // last为上一步跳了几个单位
    boolean dfs(int[] stones, int u, int last){
        if(memo[u][last] != null) return memo[u][last];
        if(u == n - 1) return memo[u][last] = true;

        for(int i = -1; i <= 1; i++){
            int cur = i + last;
            if(cur > 0){
                int next = stones[u] + cur;
                if(map.containsKey(next) && dfs(stones, map.get(next), cur)){
                    return memo[u][last] = true;
                }
            }
        }
        return memo[u][last] = false;
    }
}

• 用哈希表做标记 + 二元组哈希

class Solution {
    Map<Integer,Integer> map = new HashMap<>();
    Map<Integer,Boolean> memo = new HashMap<>();
    int n;
    public boolean canCross(int[] stones) {
        n = stones.length;
        for(int i = 0; i < n; i++){
            map.put(stones[i], i);
        }
        return dfs(stones, 0, 0);
    }

    // a乘上b的最大值，再加上b，即可对二元组进行哈希
    int base(int a, int b){
        return a * 2000 + b;
    }

    // u为当前走到的位置下标
    // last为上一步跳了几个单位
    boolean dfs(int[] stones, int u, int last){
        if(memo.containsKey(base(u, last))) return memo.get(base(u, last));
        if(u == n - 1) return true;

        for(int i = -1; i <= 1; i++){
            int cur = i + last;
            if(cur > 0){
                int next = stones[u] + cur;
                if(map.containsKey(next) && dfs(stones, map.get(next), cur)){
                    memo.put(base(u, last), true);
                    return memo.get(base(u, last));
                }
            }
        }
        memo.put(base(u, last), false);
        return memo.get(base(u, last));
    }
}

算法3

(动态规划)

• 考虑把记忆化搜索的代码改成dp
• 状态定义：f[i][k]表示青蛙当前处于下标i，且上一步跳了k个距离，答案为f[n-1][1] || ... || f[n-1][n]

• 状态转移：枚举每一个上一步跳到的位置j，跳到上一步位置的距离可以为k-1,k和k+1，所以f[i][k] = f[j][k-1] || f[j][k] || f[j][k+1]，并且跳跃距离k = stones[i] - stones[j]必须满足k <= j + 1，因为第j个位置最多只能跳跃j+1个距离

• 时间复杂度：$O(n^2)$

Java代码

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        // f[i][j]表示当前在i，上一步跳了j能否到达
        boolean[][] f = new boolean[n][n];
        f[0][0] = true;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                // j跳到i用了k步
                int k = stones[i] - stones[j];
                if(k <= j + 1){
                    f[i][k] = f[j][k-1] || f[j][k] || f[j][k+1];
                }
            }
        }
        for(int i = 1; i < n; i++){
            if(f[n-1][i]) return true;
        }
        return false;
    }
}

算法4

(记忆化BFS)

• 状态之间存在拓扑序的超时dfs问题可以改成记忆化bfs

• 时间复杂度：$O(n^2)$

Java代码

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            map.put(stones[i], i);
        }
        Queue<int[]> q = new LinkedList<>();
        boolean[][] st = new boolean[n][n];
        q.offer(new int[]{0, 0});
        st[0][0] = true;
        while(q.size() != 0){
            int[] t = q.poll();
            int idx = t[0], last = t[1];
            if(idx == n - 1) return true;
            for(int i = -1; i <= 1; i++){
                int cur = last + i;
                if(cur > 0 && map.containsKey(stones[idx] + cur)){
                    int a = map.get(stones[idx] + cur), b = cur;
                    if(!st[a][b]){
                        q.offer(new int[]{a, b});
                        st[a][b] = true;
                    }
                }
            }
        }
        return false;
    }
}