leetcode.403 青蛙过河-回溯解法/dp解法-一一网

【摘要】题目：

一只青蛙想要过河。假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。青蛙可以跳上石子，但是不可以跳入水中。给你石子的位置列表 stones（用单元格序号升序表示），请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时，青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只…

题目：

一只青蛙想要过河。假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。
青蛙可以跳上石子，但是不可以跳入水中。给你石子的位置列表 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
题源：https://leetcode-cn.com/problems/frog-jump/

解法1：优化DFS记忆化搜索：

先上代码和结果，后面解释：

class Solution { public boolean canCross(int[] stones) { // 回溯法递归 int  n = stones.length; Map<Integer, Boolean> map = new HashMap<>(); return DFS(stones, 0, 0, n, map); } /** *  index: 表示现在所处的索引 *  k: 表示上一步跳跃了几个单元格 *  n: 表示数组长度 *  map: 表示经历过的状态 **/ private boolean DFS(int[] stones, int index, int k, int n, Map<Integer, Boolean> map) { // 递归终止条件 // System.out.println("index:" + index + "  k:" + k); if (index == n - 1) { return true; } int key = index * 1000 + k; if (map.containsKey(key)) { return false; } else { map.put(key, true); } for (int i = index + 1; i < n; i++) { int gap = stones[i] - stones[index]; if (gap >= k-1 && gap <= k + 1) { if (DFS(stones, i, gap, n, map)) { return true; } } else if (gap > k + 1) { break; } else { continue; } } return false; }
}

  
 
  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
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43

在这里插入图片描述

思路：
最简单直接的解法是直接使用DFS算法，对所有可能的跳跃情况（假设上一步跳跃的步数为i，则这一步的可能性有i，i-1，i+1三种）进行遍历，直到找到可行的方法为止，如果没找到可行解就返回false；
但是如果不进行优化的话，该算法的时间复杂度在最坏情况下是指数级的，因此进行优化；

首先对回溯的情况进行分析，我们已知每一步都有三种可能性，那么，在这些可能性中是否存在重复的情况呢？答案是肯定的。

下面举个栗子：
假设第一步是从位置1开始，由题意得第一步仅能跳一个单位到达位置2，那么在第二步我们可以有0，1，2这三种步数的选择，分别到达2，3，4这三个位置，从2，3，4这三个位置开始，每个位置又分别都有三种可能性，但由于青蛙不能往回走，所以在走的上一步的步数k为0时，k-1 = -1代表往回走，是不合法的，因此下面举例时省略掉这种情况

按这样的格式（index(位置)，k(步数)）来记录的话，如果给定的数组是{0,1,2,3,4,5}的话，会产生如下的可能性：
0 0
1 1
2 1
3 1
4 1
5 1
5 2
4 2
5 1 (重复)
3 2
4 1 (重复)
5 1 (重复)
5 2 (重复)
解释：
我们可以清晰的看到有一定量的可能性产生了重复，这就是我们需要优化的地方
我们可以采用常用的记忆化方法进行优化，采用map记录遇到过的结果，给每一个第一次遇到的结果的index和k的值构造一个唯一的key（类似于hashmap？），并且给key对应的value赋值为true代表曾经遇见过这个结果，下次再遇到相同的结果，就从map中直接取对应的计算结果就可以。

但实际上，如果这个结果是第二次出现，就完全没必要加入进行额外的计算了；因为这个结果之所以不是第一次出现，是因为上一次它一定是返回false的，只有返回false才会继续搜索其他分支的可能性；因此，遇到重复的结果，直接返回false就可以了

做到心中有图，做剪枝优化思路自然清晰~

解法2：动态规划

老规矩，先上代码和结果，下面讲思路

class Solution { public boolean canCross(int[] stones) { int n = stones.length; boolean dp[][] = new boolean[n][n+1];//标记数组，第n个石头能否跳n+1步 dp[0][1] = true;//第0个石头可以跳1步 for(int i=1;i<n;i++) { boolean flag = false; for(int j = i-1;j>=0;j--) { int step = stones[i] - stones[j]; if(step > i) { break; } if(dp[j][step] == true) {//要跳到石头j需要的步数 flag = true; dp[i][step-1] = true; dp[i][step] = true; dp[i][step+1] = true; } } if(i == n-1 && flag == false) {//无法从前面任意石头跳到终点 return false; } } return true; }
}

  
 
  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

在这里插入图片描述

思路：
首先缩小问题规模…如果青蛙要到下一个点，那么必定存在下列条件点之一（或者多个）

[ 1 ] 上一个石头和下一个石头距离为k
[ 2 ] 上一个石头和下一个石头距离为k+1
[ 3 ] 上一个石头和下一个石头距离为k-1

然后，按照已有的条件创建一个dp数组：

dp[i][k]

含义：
i表示每个石头的编号
k表示上一次跳跃的距离
初始化（边界条件）：dp[0][0] = true（青蛙从第1个石头开始跳，所以0号石头必定存在）
由此，我们可以递推出动态规划的状态转移方程：

dp[i][k] = dp[ j ][k – 1] || dp[ j ][k] || dp[ j ][k + 1]
在状态转移方程中，j的含义是上一个石子的下标，其范围必然是小于1的
也就是说 j 满足stones[ i ] – stones[ j ] = 这一条件

对动态规划进行优化后的解法：

（代码在思路下面）
然后，我们可以再找一些规律来优化动态规划的运行效率

结论1.现在所处的石子编号为 i 时，上一次的跳跃距离k 必定满足k <= i;

解释：当青蛙在位置0的时候（也就是第一个石子上的时候），它上一次跳跃的距离k已经被限制为0，之后的每次跳跃，对于满足条件的分支，石子编号的增加个数至少为1，但每次跳跃的距离至多增加1（按照每次分别是k、k+1，k+2这样的最远跳跃来看）
在青蛙跳了n次后，青蛙现在所处的石子的位置i一定是>=n的，而上一次跳跃的距离k一定是<=n的，因此可以通过n推出：i>=n>=k,所以i>=k;
这样的话我们可以从后向前遍历上一次所在的石子编号j，当上一次跳跃距离k 超过了j+1时，我们即可以停止跳跃，因为在第 j 个石子上我们至多只能跳出j+1的距离

结论2.当第 i 个石子与第 i-1个石子的距离超过 i 时，青蛙必定无法到达终点。

解释：由结论1可知，当青蛙到达第n个石子的时候，它的上一次跳跃距离k至多为n，也就是说它的下一次跳跃最多能跳出k+1的距离，而距离n号石子最近的石子为n+1号石子，如果它们相距的距离大于k+1，可以直接判定青蛙跳不到下一步；这步可以在刚开始就进行遍历，如果发现了这样过远的石子，直接返回false就可以，可以有效缩减问题规模
代码如下

class Solution { public boolean canCross(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 j = i - 1; j >= 0; j--) { int k = stones[i] - stones[j]; if (k > j + 1) { break; } dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1]; if (i == n - 1 && dp[i][k] == true) { return true; } } } return false; }
}

  
 
  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