jump-game（跳跃游戏）

题目1

给定一个非负整数数组，您最初位于数组的第一个索引处。

数组中的每个元素表示您在该位置的最大跳跃长度。

确定您是否能够达到最后的索引。

例如：
A = [2,3,1,1,4]，returntrue。

A = [3,2,1,0,4]，returnfalse。

代码实现

/**
 *贪心算法
 */
public class Solution {
    public boolean canJump(int[] A) {
        if(A==null || A.length<=1) return true;
        return canJump(A,0);
    }
    public boolean canJump(int [] A, int index){
        if(index==A.length-1) return true;
        if(A[index]==0) return false;
        if(A[index]>=A.length-1-index) return true;
        boolean flag=false;
        for(int i=1;i<=A[index];i++){
            flag= flag || canJump(A,index+i);
        }
        return flag;
    }
}

题目2

给定一个非负整数数组，您最初位于数组的第一个索引处。

数组中的每个元素表示您在该位置的最大跳跃长度。

你的目标是达到最小跳跃次数的最后一个索引。

例如：
给定数组A = [2,3,1,1,4]

跳到最后一个索引的最小跳数为2。 （从索引0到1跳转1步，然后3步到最后一个索引。）

代码实现1

/**
 *贪心算法
 *从开始位置到开始位置能走到的最大距离之间构成了一块区域，然后我们开始一格一格走，
 *每走一下刷新一下当前这块区域能到的最大位置，如果走到从开始位置走到了furthest_pre那我们也刷新出了最大的furthest_cur,  
 *如果furthest_cur比终点大，那恭喜！再跳一不就到终点了！可以开始跳一步咯！
 *然后重复上述的动作，直到到达终点。
 */
public int jump(int[] A) {
        int[] dp = new int[A.length]; // dp存放都到各点的最小步数
        for (int i = 0; i < dp.length; i ++) {
            int maxPosition = Math.min(i + A[i], A.length - 1); // 从i点出发能走的最远距离
            for (int j = i + 1; j <= maxPosition; j ++) {
                if(dp[j] == 0) dp[j] = dp[i] + 1; // 如果位置没被走过,则到达j点的步数为dp[i]+1
            }
            if(dp[A.length - 1] != 0) break; // 当第一次到达终点时,肯定是到达终点最短的步数
        }
        return dp[A.length - 1];
    }

代码实现2

/**
 *动态规划
 */
 public class Solution {
    public int jump(int[] A) {
        if(A==null || A.length<=1) return 0;
        int n=A.length;
        int [] dp=new int [n];//d[i]表示数组中位置i处到最后一个位置所需的最少步数
        //初始化数组
        dp[n-1]=0;
        for(int i=0;i<n-1;i++){
            if(A[i]+i>=n-1) dp[i]=1;
            else dp[i]=A.length;
        }
        //状态转移方程
        for(int i=n-2;i>=0;i--){
            if(dp[i]!=1){
                for(int j=1;j<=A[i] && j+i<=n-1;j++){
                    dp[i]=Math.min(dp[i],dp[i+j]+1);
                }
            }
        }
        return dp[0];
    }
}

题目1来自牛客网leetcode
题目2来自牛客网leetcode