给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。
分析：
方法一：基于动态规划的做法，时间复杂度O(n^2)。数组dp[i]表示能否到达下标为i的位置，对于从下标i=1开始的每一个位置，都从下标j=0开始到i-1判断能否到达j，并且判断从j开始最远能否跳到或超过i的位置，如果能，则令dp[i]=true，并退出j的循环。最后只需要看dp[A.length-1]即能否达到数组最后一个位置。
public boolean canJump(int[] A) { // write your code here boolean[] dp=new boolean[A.length]; //dp[i]表示能否到下标为i的位置 dp[0]=true; for(int i=1;i<A.length;i++){ for(int j=0;j<i;j++){ if(dp[j]&&j+A[j]>=i){ //首先能到下标为j的位置，并且判断从j开始最远能否跳到或超过i的位置 dp[i]=true; break; } } } return dp[A.length-1]; }方法二：基于贪心策略，时间复杂度为O(n)。用farthest保存当前能到达的最远位置，遍历数组，如果当前位置小于等于最远能到的位置（即可达）且从当前位置出发能到达的最远位置大于等于当前的farthest，那么更新farthest。最后判断farthest是否大于等于数组长度即可。 public boolean canJump1(int[] A) { if(A==null || A.length==0) return false; int farthest=A[0]; //下标为0位置所能到的最远的位置, farthest一直保存当前能到的最远位置 for(int i=1;i<A.length;i++){ if(i<=farthest && i+A[i]>=farthest){ farthest=A[i]+i; } } return farthest>=A.length-1; //最后看最远距离能否超过数组长度 }给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
分析：采用动态规划的方法，方法同第一题类似， 数组dp[i]表示能到下标为i的位置所需要的最小步数，对于从下标i=1开始的每一个位置，都从下标j=0开始到i-1判断从j开始最远能否跳到或超过i的位置，如果能，则dp[i]=dp[j]+1，并退出j的循环。因为不必往后继续循环是因为越靠近起点的点(j越靠近0），必然步数越少，因为往后的步数都是基于前面的点。最后只需要返回dp[A.length-1]即可，即到下标为A.length-1的位置所需要的最小步数。 public int jump(int[] A) { // write your code here if(A==null || A.length==0) return -1; int[] step=new int[A.length]; step[0]=0; //step[i]表示到下标i时所需要的最小步数 for(int i=1;i<A.length;i++){ for(int j=0;j<i;j++){ if(j+A[j]>=i){ step[i]=step[j]+1; //不必往后继续循环的原因是越靠近起点的点(j越接近0),必然步数越少，因为往后的步数更新都是基于前面的点 break; } } } return step[A.length-1]; }