本文主要是介绍JAVA算法：Jump Game 45题和55题算法详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
在LeetCode中45题和55题是关于Jump Game的问题，下面来看看这两道题目的求解方法。
这两个题目的区别是：55题的要求判断你是否能够从开始位置跳到结束位置；而45题的要求是求你从开始位置能够跳到结束位置的最小跳跃次数。。
原题链接：
55. Jump Game https://leetcode.com/problems/jump-game/
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
45. Jump Game II https://leetcode.com/problems/jump-game-ii/
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
问题求解：从起始位置能够跳跃到最后的终止位置
算法分析：回溯算法（Backtracking）
采用回溯算法（Backtracking），这是一个效率低下的解决方案。
思路：
尝试从第一个位置到最后一个位置的每一个跳跃模式。
从第一个位置开始，跳到所有可以到达的索引。
重复这个过程，直到到达最后一个索引。
卡住时，回退。
算法设计：
/** 从index为0的位置开始起跳* */public boolean canJump(int[] nums) {return canJumpFromPosition(0, nums);}/** 采用回溯算法（Backtracking），这是一个效率低下的解决方案。* 思路：* 尝试从第一个位置到最后一个位置的每一个跳跃模式。* 从第一个位置开始，跳到所有可以到达的索引。 * 重复这个过程，直到到达最后一个索引。 * 卡住时，回退。*/public boolean canJumpFromPosition(int position, int[] nums) {//如果到达结束位置，则返回trueif (position == nums.length - 1) {return true;}int furthestJump = Math.min(position + nums[position], nums.length - 1);for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {if (canJumpFromPosition(nextPosition, nums)) {return true;}}return false;}这个算法虽然可以得到正确的结果，但是在LeetCode上提交时超时！
算法设计：贪心算法（Greedy）
/** 贪心算法(Greedy)* */public boolean canJump(int[] nums) {int lastPos = nums.length - 1;for (int i = nums.length - 1; i >= 0; i--) {if (i + nums[i] >= lastPos) {lastPos = i;System.out.println("lastPos = " + lastPos);}}return lastPos == 0;}提交之后，Accepted！
算法设计：贪心算法（Greedy）设计
维护一个当前能跳到的最大值maxJump,
若是maxJump 已经>=nums.length-1, 说明能跳到最后一个点，return true.
若是过程中maxJump <= i, 说明跳到当前点便不能往前，跳出loop, return false.
/** 贪心算法* 维护一个当前能跳到的最大值maxJump, * 若是maxJump 已经>=nums.length-1, * 说明能跳到最后一个点，return true.* 若是过程中maxJump <= i, * 说明跳到当前点便不能往前，跳出loop, return false.* */public boolean canJump(int[] nums) {int n = nums.length;// maxJump是维护的当前能跳到的最大位置int maxJump = 0;// for (int i = 0; i < n && i <= maxJump; ++i)// maxJump = Math.max(nums[i] + i, maxJump);for (int i = 0; i < n; i++) {// i>maxJump表示无法到达i的位置,失败// maxJump >= (n - 1),此时的距离已经足够到达终点，成功if (i > maxJump || maxJump >= (n - 1))break;// nums[i]+i当前跳最远距离 maxJump为i之前跳最远距离maxJump = Math.max(maxJump, i + nums[i]);}return maxJump >= (n - 1);}算法设计：动态规划（DP）
每次跳跃选择往最远处跳跃，如果最后能够跳到数组最后一位或者最后一位之后，
那么一定存在一种跳跃方式正好跳到最后一位上。
/** 每次跳跃选择往最远处跳跃，如果最后能够跳到数组最后一位或者最后一位之后，* 那么一定存在一种跳跃方式正好跳到最后一位上* *//** 动态规划* */public boolean canJump(int[] nums) {int n = nums.length;// dp[i]表示当前跳跃的最大距离int dp[] = new int[n];dp[0] = nums[0];// i表示当前距离，也是下标for (int i = 1; i < n; i++) {// i点可达if (i <= dp[i - 1])dp[i] = Math.max(dp[i - 1], i + nums[i]);elsedp[i] = dp[i - 1];}return dp[n - 1] >= (n - 1);}问题求解：从起始位置能够跳跃到最后的终止位置时，最小的跳跃次数
算法设计：贪心算法（Greedy）
/** 给定一个非负整数数组，给定的初始化位置在数组的起始位置。* 数组中的每个元素代表着你能都在此位置跳跃的最大的距离。* 你的目标是用最少的跳跃数达到数组的末尾。* 算法：贪心* */public int jump(int[] nums) {if (nums.length <= 1)return 0;if (nums[0] == 0)return -1;// 记录当前活动距离int reach = nums[0];int steps = 0, start = 0;for (; start < nums.length && start <= reach;) {++steps;if (reach >= nums.length - 1) {return steps;}// nextMax表示下一步能到达的最远距离int nextMax = 0;// 在当前start和reach之间，找下一步能到达最远的距离的下标for (int i = start; i <= reach; ++i) {if ((i + nums[i]) > nextMax) {nextMax = i + nums[i];start = i;}}reach = nextMax;}return -1;}算法设计：贪心算法（Greedy）
public int jump(int[] nums) {if (nums == null || nums.length == 0) {return -1;}// cur是维护的当前能跳到的最大位置// 第step+1步，能到达的最远距离int cur = 0;// last是指从之前的点能reach到得最远位置// 已经可以到达的最大距离int last = 0;int step = 0;for (int i = 0; i < nums.length/* && i <= cur */; i++) {// 当i 大于之前点能碰到的最大位置时，就需要跳一步，// 并把last更新为cur.if (i > last) {step++;last = cur;}// 计算step+1的最大距离cur = Math.max(cur, nums[i] + i);}// 最后返回若是cur能到最后一个元素，就返回step,// 若是到不了，就说明根本走不到最后一步，返回-1.return cur < nums.length - 1 ? -1 : step;}更详细的分析，参考LeetCode上的Article栏目分析博文，链接地址：
https://leetcode.com/articles/jump-game/
还可以参考博主 FserSuN 的文章，链接地址：
https://blog.csdn.net/Revivedsun/article/details/52951765
这两篇文章写得非常棒！
这篇关于JAVA算法：Jump Game 45题和55题算法详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
