LeetCode--55. Jump Game

本文主要是介绍LeetCode--55. Jump Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://leetcode.com/problems/jump-game/

这是个十分有趣的题目。从起点（数组索引0）出发，移动k（k<=nums[0]）个位置到达下一个位置(数组索引为i)，继续移动k（k<=nums[i]）个位置，就这样看是否有一条走法能到达终点（数组索引nums.length-1）。当走到某个位置i时nums[i]==0时就意味着这个走法行不通了！可以看到理论上每一个位置i上都有nums[i]个选择的步数。

我的思路：用回溯法来暴力搜索，在当前到达的位置状态i上，有1:nums[i]种选择（只要nums[i]+i<nums.length），然后就进入下一个（位置）状态继续搜索。

class Solution {public static boolean canJump(int[] nums) {return recursion(0,nums);}public static boolean recursion(int index,int[] nums){if(index==nums.length-1)return true;if(nums[index]==0)return false;boolean ret=false;for(int i=1;i<=nums[index];i++)if(index+i<nums.length)ret=ret || recursion(index+i,nums);return ret;}
}

时间复杂度：O(2^n)，从起点到达终点有2^n的走法（理论上限）

空间复杂度：O(n)，递归时的栈内存开销

暴力是真暴力，就是TLE了！！！

其实审查上面的过程，到达位置状态i的策略选择可以由很多很多种，而后面从i为起点的搜索只需要进行一次，然而我的算法存在大量重复。

看了Solutions后豁然开朗，https://leetcode.com/problems/jump-game/solution/这篇题解将回溯、动态规划讲的很全面很详细了，下面借鉴这篇题解写写自己的理解。

上面的步骤在实践中可以稍微优化一下,从较大调步开始搜索更快到达终点，但算法理论复杂度没变。

for(int i=nums[index];i>0;i--)

自顶向下的动态规划：

用一个memo数组存储位置i对于终点的可达性（accesibility），终点对于其本身是可达的，首先将memo数组memo[0:nums.length-2]=Unknown;

enum Mark{Accessible,Inaccessible,Unknown
}public class Solution {public Mark[] memo;public boolean canJump(int[] nums) {memo=new Mark[nums.length];for(int i=0;i<memo.length;i++)memo[i]=Mark.Unknown;memo[nums.length-1]=Mark.Accessible;return canJumpFromIndex(0,nums);}public boolean canJumpFromIndex(int index,int[] nums){if(memo[index]!=Mark.Unknown)return memo[index]==Mark.Accessible? true:false;int min_index=Math.min(nums[index]+index,nums.length-1);for(int i=min_index;i>=index+1;i--){if(canJumpFromIndex(i,nums)){memo[index]=Mark.Accessible;return true;}}memo[index]=Mark.Inaccessible;return false;   }
}

时间复杂度为：O(n^2),因为对于每个状态位置i，都有可能将[i+1：nums.length-1]遍历一遍

空间复杂度：O(n),递归的栈空间开销O(n)，额外数组开销O(n)

 

自底向上的动态规划：自底向上一般能够将递归改成循环的形式，而且能够减少中间重复的计算

确定第i个位置的可达性只需要检查第[i+1,i+min(nums[i]+i,nums.length-1)]的位置上的可达性，真是tricky！！！

public class Solution {public Mark[] memo;public boolean canJump(int[] nums) {memo=new Mark[nums.length];for(int i=0;i<memo.length;i++)memo[i]=Mark.Unknown;memo[nums.length-1]=Mark.Accessible;for(int i=nums.length-2;i>=0;i--){int max_index=Math.min(nums[i]+i,nums.length-1);for(int j=max_index;j>i;j--){if(memo[j]==Mark.Accessible){memo[i]=Mark.Accessible;break;}}}return memo[0]==Mark.Accessible?true:false;}
}enum Mark{Accessible,Inaccessible,Unknown
}

最终极的方法的思路就是：要确定当前某个位置i的可达性，只需要找到大于i且具有可达性的最小的位置j，如果i到j可达（nums[i]+i>=j,这里如果nums[i]+i>nums.length-1就更能说明可以到达了)则i也可达，并将i设置为“具有可达性的最小的位置”，让我们一起欣赏一下这个代码：

public class Solution {public boolean canJump(int[] nums) {int minPosition=nums.length-1;for(int i=nums.length-1;i>=0;i--){if(nums[i]+i>=minPosition)minPosition=i;}return minPosition==0;} 
}

 

这篇关于LeetCode--55. Jump Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---