一.跳跃游戏简单介绍
1. 跳跃游戏简单介绍
跳跃游戏是一种典型的算法题目,经常是给定一数组arr,从数组的某一位置i出发,根据一定的跳跃规则,比如从i位置能跳arr[i]步,或者小于arr[i]步,或者固定步数,直到到达某一位置,可能是数组的最后一个位置,也有可能是某一特别的数值处,也有可能在这个过程中,可能需要求解可能存在的最大值或者最小值。
对于跳跃游戏类的题目,经常使用贪心、动态规划、dfs、bfs等方法解决,对于可以使用dfs解决的题目,经常也可以使用动态规划,但一般贪心可以有更好的时间复杂度和空间复杂度。还有经常使用的动态规划剪枝、前缀和、滑动窗口和BFS,由于在大部分情况下,能用DFS解决的题目都可以用BFS解决,且两种方法有基本相同的复杂度,尤其是在跳跃游戏这类题目中,可以视为一种方法。
本文借青蛙酱主要复习动态规划三部曲。
2.跳跃游戏典型题目
(1)leetcode70 爬楼梯
(2)leetcode剑指 Offer 10- II. 青蛙跳台阶问题
(3)剑指 Offer II 088. 爬楼梯的最少成本
(4) leetcode55 跳跃游戏
(5)leetcode45 跳跃游戏 II
(6) leetcode1306 跳跃游戏 III
(7)leetcode1696 跳跃游戏 VI
(8)leetcode1871 跳跃游戏 VII
(9)leetcode1413 逐步求和得到正数的最小值
以上部分,请见:
跳跃游戏 (贪心/动态规划/dfs)
跳跃游戏 (动态规划剪枝/前缀和/滑动窗口/BFS剪枝)
3.动态规划三步曲复习
Java-算法-动态规划
二.跳跃游戏相关专题-青蛙酱🐸的奇妙冒险
1. 剑指 Offer 10- II 青蛙跳台阶问题
见 一.2.(2)
2. leetcode 2498 青蛙过河 II
给你一个下标从 0 开始的整数数组 stones ,数组中的元素 严格递增 ,表示一条河中石头的位置。
一只青蛙一开始在第一块石头上,它想到达最后一块石头,然后回到第一块石头。同时每块石头 至多 到达 一次。
一次跳跃的 长度 是青蛙跳跃前和跳跃后所在两块石头之间的距离。
更正式的,如果青蛙从 stones[i] 跳到 stones[j] ,跳跃的长度为 |stones[i] - stones[j]| 。
一条路径的 代价 是这条路径里的 最大跳跃长度 。
请你返回这只青蛙的 最小代价 。
输入:stones = [0,2,5,6,7]
输出:5
解释:上图展示了一条最优路径。
这条路径的代价是 5 ,是这条路径中的最大跳跃长度。
无法得到一条代价小于 5 的路径,我们返回 5 。
输入:stones = [0,3,9]
输出:9
解释:
青蛙可以直接跳到最后一块石头,然后跳回第一块石头。
在这条路径中,每次跳跃长度都是 9 。所以路径代价是 max(9, 9) = 9 。
这是可行路径中的最小代价。
class Solution {
public int maxJump(int[] stones) {
if(stones.length <= 2) return stones[1]-stones[0];
int ans = stones[2]-stones[0];
for(int i = 2; i < stones.length; i++) ans = Math.max(ans,stones[i]-stones[i-2]);
return ans;
}
}
本题小结:
(1)首先思考,是跳所有的石头产生的结果最小还是漏过一些石头产生的结果最小,很显然,把所有的石头都跳过,在中间相当于插值,所产生的结果才有可能是最小的,即min(跳所有的石头)<=min(漏过一些石头)
(2)一句话贪心证明:大于三个的一段距离都可以进行分解成更小的段
3. leetcode 403. 青蛙过河
一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。
给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一块石子上)。开始时, 青蛙默认已站在第一块石子上,并可以假定它第一步只能跳跃 1 个单位(即只能从单元格 1 跳至单元格 2 )。
如果青蛙上一步跳跃了 k 个单位,那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意,青蛙只能向前方(终点的方向)跳跃。
输入:stones = [0,1,3,5,6,8,12,17]
输出:true
解释:青蛙可以成功过河,按照如下方案跳跃:跳 1 个单位到第 2 块石子,
然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子,
然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后,
跳 5 个单位到第 8 个石子(即最后一块石子)。
输入:stones = [0,1,2,3,4,8,9,11]
输出:false
解释:这是因为第 5 和第 6 个石子之间的间距太大,没有可选的方案供青蛙跳跃过去。
DFS
class Solution {
int[] stones;
HashMap<Integer,Integer> map = new HashMap<>();
boolean flag = false;
public boolean canCross(int[] stones) {
this.stones = stones;
int len = stones.length;
if(stones[1] >= 2) return false;
for(int i =0; i < len; i++){
map.put(stones[i],i);
}
dfs(1,1,len);
return flag;
}
public void dfs(int index, int k, int len){
if(index == len-1){
flag = true;
return;
}
if(k == 1){
if(stones[index]+1 <= stones[len-1]){
if(map.containsKey(stones[index]+1)){
dfs(map.get(stones[index]+1),1,len);
}
}
if(stones[index]+2 <= stones[len-1]){
if(map.containsKey(stones[index]+2)){
dfs(map.get(stones[index]+2),2,len);
}
}
}
else{
if(stones[index]+k-1 <= stones[len-1]){
if(map.containsKey(stones[index]+k-1)){
dfs(map.get(stones[index]+k-1),k-1,len);
}
}
if(stones[index]+k <= stones[len-1]){
if(map.containsKey(stones[index]+k)){
dfs(map.get(stones[index]+k),k,len);
}
}
if(stones[index]+k+1 <= stones[len-1]){
if(map.containsKey(stones[index]+k+1)){
dfs(map.get(stones[index]+k+1),k+1,len);
}
}
}
}
}
当然dfs是不能通过的
记忆化搜索
class Solution {
int[] stones;
HashMap<Integer,Integer> map = new HashMap<>();
boolean flag = false;
boolean[][] memo;
public boolean canCross(int[] stones) {
this.stones = stones;
int len = stones.length;
if(stones[1] >= 2) return false;
for(int i =0; i < len; i++){
map.put(stones[i],i);
}
memo = new boolean[len][len+1];
dfs(1,1,len);
return flag;
}
public void dfs(int index, int k, int len){
if(index == len-1){
flag = true;
return;
}
if(memo[index][k]) return;
if(k == 1){
if(map.containsKey(stones[index]+1)){
dfs(map.get(stones[index]+1),1,len);
}
if(map.containsKey(stones[index]+2)){
dfs(map.get(stones[index]+2),2,len);
}
}
else{
if(map.containsKey(stones[index]+k-1)){
dfs(map.get(stones[index]+k-1),k-1,len);
}
if(map.containsKey(stones[index]+k)){
dfs(map.get(stones[index]+k),k,len);
}
if(map.containsKey(stones[index]+k+1)){
dfs(map.get(stones[index]+k+1),k+1,len);
}
}
memo[index][k] = true;
}
}
实际上以上的解法可以看出很多代码是可以重复的,可以写成for循环,堆结果合并,并处理k=1的特殊情况。
Ref.[1]:
DFS
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public boolean canCross(int[] ss) {
int n = ss.length;
// 将石子信息存入哈希表
// 为了快速判断是否存在某块石子,以及快速查找某块石子所在下标
for (int i = 0; i < n; i++) {
map.put(ss[i], i);
}
// check first step
// 根据题意,第一步是固定经过步长 1 到达第一块石子(下标为 1)
if (!map.containsKey(1)) return false;
return dfs(ss, ss.length, 1, 1);
}
/**
* 判定是否能够跳到最后一块石子
* @param ss 石子列表【不变】
* @param n 石子列表长度【不变】
* @param u 当前所在的石子的下标
* @param k 上一次是经过多少步跳到当前位置的
* @return 是否能跳到最后一块石子
*/
boolean dfs(int[] ss, int n, int u, int k) {
if (u == n - 1) return true;
for (int i = -1; i <= 1; i++) {
// 如果是原地踏步的话,直接跳过
if (k + i == 0) continue;
// 下一步的石子理论编号
int next = ss[u] + k + i;
// 如果存在下一步的石子,则跳转到下一步石子,并 DFS 下去
if (map.containsKey(next)) {
boolean cur = dfs(ss, n, map.get(next), k + i);
if (cur) return true;
}
}
return false;
}
}
记忆化搜索
class Solution {
Map<Integer, Integer> map = new HashMap<>();
// int[][] cache = new int[2009][2009];
Map<String, Boolean> cache = new HashMap<>();
public boolean canCross(int[] ss) {
int n = ss.length;
for (int i = 0; i < n; i++) {
map.put(ss[i], i);
}
// check first step
if (!map.containsKey(1)) return false;
return dfs(ss, ss.length, 1, 1);
}
boolean dfs(int[] ss, int n, int u, int k) {
String key = u + "_" + k;
// if (cache[u][k] != 0) return cache[u][k] == 1;
if (cache.containsKey(key)) return cache.get(key);
if (u == n - 1) return true;
for (int i = -1; i <= 1; i++) {
if (k + i == 0) continue;
int next = ss[u] + k + i;
if (map.containsKey(next)) {
boolean cur = dfs(ss, n, map.get(next), k + i);
// cache[u][k] = cur ? 1 : -1;
cache.put(key, cur);
if (cur) return true;
}
}
// cache[u][k] = -1;
cache.put(key, false);
return false;
}
}
以上四种解答,两种写法,在本质上一样,枚举在一个位置可能的情况,进行递归,DFS都不能通过,使用记忆化搜索降低时间复杂度,走过的路不再走。
动态规划
class Solution {
public boolean canCross(int[] ss) {
int n = ss.length;
// check first step
if (ss[1] != 1) return false;
boolean[][] f = new boolean[n + 1][n + 1];
f[1][1] = true;
for (int i = 2; i < n; i++) {
for (int j = 1; j < i; j++) {
int k = ss[i] - ss[j];
// 我们知道从位置 j 到位置 i 是需要步长为 k 的跳跃
// 而从位置 j 发起的跳跃最多不超过 j + 1
// 因为每次跳跃,下标至少增加 1,而步长最多增加 1
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;
}
}
参考来源 Ref.
[1] leetcode 宫水三叶 【宫水三叶】一题四解 : 降低确定「记忆化容器大小」的思维难度