LeetCode 55 Jump Game从回溯到动态规划

背景

动态规划是一个降低时间的很有效的方法,通常一个可以使用递归从上到下来解决的题目,必定可以转化为动态规划,从下往上计算,并通过设置一个数组存放子问题的解,来降低问题的求解步骤。LeetCode上的第55题可以使用回溯法和动态规划来解决,但回溯法会造成栈溢出,下面讲解我的解题思路。

题目介绍

给定一个正整数的数组,你起始的位置位于数组的第一个下标处(也就是0),数组中的每个元素代表在该位置可以跳跃的最大距离(只能向index增加的方向跳跃),判断是否有一条跳跃路径,可以使得你跳到最后一个下标处(也就是length-1)。
示例:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

原题链接 55. Jump Game

题目分析

相信玩过类似大富豪这样的游戏的同学,理解起这个问题来不会太困难。它相当于有一个起点、一个目的地,从起点到目的地是一个个的格子(只能跳整数个),每个格子规定了当前格子能够跳跃的最大值,让我们来求是否有一条路径可以从起点到终点,文字不太直观,下面我们通过图来展示一下上面的示例。

当 A = [2,3,1,1,4]

由上图,从0的位置最大可以跳2格,选择跳一格,到达下标为1的位置,此时最大可以跳3格,选择跳3格到达终点。因此,应该返回 true。A = [3,2,1,0,4]的情况在此不再做分析。下面开始正式解题。

Round 1

第一个回合,根据从起点到终点的特性,理所当然的想到了将问题转化为图问题,于是,我画了下图。

圆形中的数字代表下标,箭头为单向的,因此,问题转变为从0到4的图遍历。但刚定义为Node类我就卡住了。两个原因:

  • 每个节点的孩子节点(单向箭头指向的节点)个数不确定
  • 太占内存了,每个node都是一个对象

Round 1, defeated !

Round 2

虽然上面的图使我的图遍历解法宣告失败,但是却给了我另一个灵感,就是树遍历的深度优先算法,当到达叶子节点的时候,算法开始回溯,直到回到一个有没有遍历到的叶子节点,再接着向下遍历。

此问题也可以使用回溯算法进行求解,算法的核心思想如下:

  1. 从index的位置开始,取得当前能够跳跃的最大值n
  2. 让i从1到n开始遍历,循环判断当前跳i步,到达的位置是否可以到达终点
  3. 若跳i步后,index >最后的位置,则可以到达终点,返回true,否则,递归判断跳i步之后的位置是否可以到达终点
  4. 若递归返回false的话,则让i+1,进行下一步循环判断是否可以到达终点
  5. 若所有的循环和递归都返回后还没有返回true,则返回false

上面那段叙述可能连我自己也看不懂啥意思,没关系,“talk is cheap, show me the code”,下面立即上代码,一目了然。

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
import java.util.Arrays;
public class lc55 {
public static void main(String[] args) {
int[] nums = {3, 2, 1, 0, 4};
lc55 test = new lc55();
System.out.println("res ? " + test.canJump(nums));
}
boolean[] flag;
public boolean canJump(int[] nums) {
flag = new boolean[nums.length];
Arrays.fill(flag, true);
if (check(nums, 0)) {
return true;
}
return false;
}
public boolean check(int[] nums, int index) {
if(index < 0 || !flag[index]) {
flag[index] = false;
return false;
}
if(index + nums[index] + 1 >= nums.length)
return true;
int n = nums[index];
while(n > 0) {
if (check(nums, index + n)) {
return true;
}
--n;
}
flag[index] = false;
return false;
}
}

上面的代码应当返回false,结果正确,于是粘贴到LeetCode上run了一下,期望输出一致,赶紧提交吧,傻眼了,栈溢出。。。

回溯算法由于频繁的递归调用,而每次方法的调用都需要进行压榨动作,当方法的嵌套调用过深的时候,就形成了栈溢出问题,虽然算法是正确的,然而AC不了啊,下面继续优化。

Round 3

解决回溯问题的栈溢出,我们一下子就想到了将递归变成循环,因为循环是递归的逆过程。细心的朋友可能发现了,上面代码中,我已经用flag数组来存放子问题的解了,当子问题为false的时候,无需在进行判断,直接返回false,因为我们之前已经求解了一遍了。因此,结合循环和子问题两个思路,我想到了使用动态规划来解决栈溢出的问题。

动态规划最重要的就是确定子问题了,通过之前的分析,不难看出,如果从3的位置可以调到终点,而从0的位置可以跳到3的位置的话,那么从0的位置也可以跳到终点。因此,我们的动态规划算法应当是从后向前遍历的,递推公式为

1
flag[i] = flag[i+1] || flag[i+2] || ... || flag[i+n]

其中n为i位置可以跳的最大步数,有一个特殊情况,如果i+n > last_index的话,则可以直接判断flag[i]为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
27
28
29
30
31
32
33
34
35
36
import java.util.Arrays;
public class lc55 {
public static void main(String[] args) {
int[] nums = {3, 2, 1, 0, 4};
lc55 test = new lc55();
System.out.println("res ? " + test.canJump(nums));
}
boolean[] flag;
public boolean canJump(int[] nums) {
flag = new boolean[nums.length];
Arrays.fill(flag, false);
for(int i=nums.length-1; i>=0; i--) {
if(i + nums[i] + 1 >= nums.length) {
flag[i] = true;
} else {
int n = nums[i];
while(n>0) {
if (((i + n) < nums.length ) && flag[i + n]) {
flag[i] = true;
n = 0;
} else if(i+n > nums.length) {
flag[i] = true;
n = 0;
} else {
--n;
}
}
}
}
return flag[0];
}
}

这下应该稳了吧,开开心心提交上去,栈溢出倒是解决了,但是出现了一个新的问题,超时! 纳尼?! 动态规划不是不计算子问题了吗?怎么还会超时呢,这不科学!

Final Round

通过查看LeetCode上提交的错误信息,可以发现测试用例形如 [29999,29998,29997,…,4,3,2,1,1,0,0]。 聪明的你可能已经发现了,数字从后往前每一步都只加一,也就是说后一格为false的话,那向前一格,数字只增加一的话,那前一格也必定为false啊,文字不清楚,下面通过画图分析。

由上图可知,2所在的格子已经求得为false,i–到达3所在的格子,由于3后面的为2的格子求得为false,所以两个1所在的格子也为false,因此3在求解flag的时候,不需要求解2、1、1这三个格子,因为他们都为false。总结就是如果i所在的格子最大跳n格,i+1所在的格子最大跳n1格,而i+1的格子为false,则只需要求解从i+2+n1格到i+n格的子问题即可,上图中两个0所在的格子。根据这个思想,可以得到下面的优化的代码。

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
import java.util.Arrays;
public class lc55 {
public static void main(String[] args) {
int[] nums = {3, 2, 1, 0, 4};
lc55 test = new lc55();
System.out.println("res ? " + test.canJump(nums));
}
boolean[] flag;
public boolean canJump(int[] nums) {
flag = new boolean[nums.length];
Arrays.fill(flag, false);
for(int i=nums.length-1; i>=0; i--) {
if(i + nums[i] + 1 >= nums.length) {
flag[i] = true;
} else {
int n = nums[i];
if(n > 0)
flag[i] = flag[i + 1];
if(n - nums[i+1] < 2) { //若n只比nums[i+1]大1,则flag[i] = flag[i + 1];
n = 0;
}
while(n - 1 > nums[i+1]) { //只计算从i+2+n1格到i+n格的子问
if (((i + n) < nums.length ) && flag[i + n]) {
flag[i] = true;
n = 0;
} else if(i+n > nums.length) {
flag[i] = true;
n = 0;
} else {
--n;
}
}
}
}
return flag[0];
}
}

再次提交代码,终于Accept了,看到绿色的返回值真是开心

总结

分析问题和解决问题的过程是最让人兴奋的,遇到一下子解决不了的问题时,不要轻易的放弃,尝试着继续改进一下,等看到绿色的AC时,往往是最开心的一刻。而即使自己最后真的败下阵来,也没关系,这时候去看大神的解法,会让自己有更多的感受和收获,记忆也会更加的牢固。好了,毒鸡汤撒完了,我去看大神界面工整且逻辑清晰的代码去了。