2021-4-29 力扣每日一题

403 青蛙过河

问题描述：

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

​ 给你石子的位置列表 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 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。
           

思路：

​ 我们可以这么来想这个问题，先跳一格，后面有三种跳法，再接着跳，后面可以再有九种跳法，有一些跳法是走不通的，所以我们要回到原来的位置，引用到编程中，我们就需要保存之前跳过的“痕迹”，这一点很重要。

​ 那么这种“保存痕迹”基本上无外乎两种方案，一个是递归，一个就是动态规划。这两个点是我们做这种”保留痕迹“题目的思考点。

​ 既然有了两种方案，如何设计呢？

​ 我最先考虑的是没有经过化简的递归，不出意外的，它超时了。

Java代码：

/** 
* @Description: 力扣403题题解
* @return: 返回结果
* @Author: Mr.Gao
* @Date: 2021/4/29 
*/

Map<Integer,Integer> map = new HashMap<>();
int max;
public boolean canCross(int[] stones) {

    int n = stones.length;
    max = stones[n-1];
    for (int i = 0; i < n; i++) {
        map.put(stones[i],1);
    }
    if(map.getOrDefault(1,0)==0){
        return false;
    }
    return dfs(1,1);
}
public boolean dfs(int now,int step){
    if(now==max){
        return true;
    }
    if(step==0){
        return false;
    }
    boolean x1 = false;
    boolean x2 = false;
    boolean x3 = false;
    if(map.getOrDefault(now+step+1,0)!=0){
        x1 = dfs(now+step+1,step+1);
    }
    if(map.getOrDefault(now+step,0)!=0&&x1==false){
        x2 = dfs(now + step, step);
    }
    if(map.getOrDefault(now+step-1,0)!=0&&x2==false){
        x3 = dfs(now + step - 1, step - 1);
    }
    return x1||x2||x3;
}
           

• 我仔细想了想它超时的原因，在递归的时候，第一步的选择极为重要，试想，在数据很大的情况下，当第一个if进去之后，我们需要计算很多步才能到结尾。计算出true还好，一旦是false，那么这一趟的递归就是白白工作，没有给后续的计算留下任何有用的信息，所以这里虽然是遍历，但是效率太低了，复杂度几乎是指数级别的。

​ 既然找到了问题所在，那如何进行优化呢？我想，问题就是出在，我们的递归保留信息，没有为之后的递归创造方便。想要解决这个问题，就应该对题目进一步分析了。

​

​ 我们注意到，青蛙跳到某个台阶上，起关键作用的是它上一步跳了多远，也就是说假如跳到同一个位置上，如果上一步跳的都是某一个值，那么它是先跳了两格再跳了三格跳到这儿的，还是先跳了四个又跳了三格到这里来的就不重要了，也就是说在同一个位置上，如果都是跳了某一个格数到达的，这n多种情况可以合为一体。

​ 那么有了这个思路，我们就可以先申请一个数组，用来跳了几次到达某个位置的信息。

Java代码：

/** 
* @Description: 力扣403题题解
* @return: 返回结果
* @Author: Mr.Gao
* @Date: 2021/4/29 
*/
private Map<Integer,Integer> map = new HashMap<>();
//这里的x是数组的长度
int x;
//这里的rex[i][j]表示跳了j步能否跳到i的位置上
private Boolean [][] rex;
//这里是stones的一个副本，因为感觉传参的话会更浪费时间
private int[] stone;



public boolean canCross(int[] stones) {
    int n = stones.length;
    rex = new Boolean[n][n];
    x = n;
    stone = new int[n];
    //对stones进行复制
    for (int i = 0; i < n; i++) {
        stone[i] = stones[i];
    }
    
    for (int i = 0; i < n; i++) {
        //这里的关键字是值，value是他们的下标
        map.put(stones[i],i);
    }
    //如果第一步不是跳一步，直接返回false
    if(map.getOrDefault(1,0)!=1){
        return false;
    }
    //接着返回我们的递归结果
    return dfs(1,1);
}

//这里的now表示下标，step表示跳到这个下标的步数
public boolean dfs(int now,int step){
    //如果我们已经遍历到最后一个数，直接返回true即可
    if(now==x-1){
        return true;
    }
    //如果这个点我们之前访问过，那么直接返回之前访问的结果即可
    if(rex[now][step] !=null){
        return rex[now][step];
    }
    //如果now的这个位置不是走了0步上来的，我们就进入这个这里
    if(step>0){
        //temp先得到我们这个下标的值
        int temp = stone[now];
        //temp123是我们得到的下一步的下标，如果这个下标存在，我们就得到，不存在就得到-1
        int temp1 = map.getOrDefault(temp+step,-1);
        int temp2 = map.getOrDefault(temp+step-1,-1);
        int temp3 = map.getOrDefault(temp+step+1,-1);
        if(temp1!=-1&&dfs(temp1,step)){
            return rex[now][step] = true;
        }
        if(temp2!=-1&&dfs(temp2,step-1)){
            return rex[now][step] = true;
        }
        if(temp3!=-1&&dfs(temp3,step+1)){
            return rex[now][step] = true;
        }
    }
    return rex[now][step] = false;
}
           

​ 经过提交，结果是可以接受的

那么，有了递归，我们的动归应该怎么思考呢？

​ 一想到动归，最关键的就是转移方程的确立，如果我们确定好了转移方程，那么问题就已经解决了一大半。那么针对这道题，转移方程应该怎么找

​ 依旧是上面的思路，我们希望前面做的工作可以给后面的运算多点信息，这里最关键的两个点，一个是当前的位置，一个是走了几步到的这个位置。

​ 有了这两个关键点，我们就将这两个关键点进行整合即可。

​ 定义：dp[ i ] [ j ]表示的含义是：是否能做到跳了 j 格，处在 i 位置。这里跳了 j 格，说明上一次跳了 j + 1，j ， j - 1格，跳了 j 格，说明上一次的位置是满足stones[ i ] - stones[ k ] = j;这里的k表示上一次的位置。上一次的位置有了，上一次跳的步数有了，那么我们的转移方程也就有了

​ dp[ i ] [ j ] = dp[ k ] [ j-1]||dp[ k ] [ j]||dp[ k ] [ j+1]

​ 其实知道了这个转移方程，我们就可以开始编码了，但是在此之前，可以先导出几个结论，来优化我们的代码

• 「现在所处的石子编号」为 i 时，「上一次跳跃距离」j 必定满足 j<=i。
  • 因为我们第一次跳到1的位置上跳了一格，之后每次下标至少增加1，而跳的距离最多增加1。所以，在第i个位置上，上次跳的距离必定满足j<=i
• 当存在第i个石子与第i-1个石子的距离超过i时，青蛙肯定无法到达终点。
  • 根据上面的结论，最多是跳了i-1次到达第i-1的位置上，所以从i-1的位置上跳到i的位置上，最多可以跳i步，如果距离超过i步的话，就不可能跳过去所以就无法到达终点。

​ 知道了这两个结论，这里就可以进行编码了

Java代码：

/**
 * @Description: 力扣403题题解3
 * @return: 返回结果
 * @Author: Mr.Gao
 * @Date: 2021/4/29
 */

public boolean canCross3(int[] stones) {
    int n = stones.length;
    boolean[][] dp = new boolean[n][n];
    dp[0][0] = true;
    for (int i = 1; i < n; ++i) {
        if (stones[i] - stones[i - 1] > i) {
            return false;
        }
    }
    for (int i = 1; i < n; ++i) {
        for (int k = i - 1; k >= 0; --k) {
            int j = stones[i] - stones[k];
            if (j > k + 1) {
                break;
            }
            dp[i][j] = dp[k][j - 1] || dp[k][j] || dp[k][j + 1];
            if (i == n - 1 && dp[i][j]) {
                return true;
            }
        }
    }
    return false;
}
           

• 虽迟但到

​