跳跃游戏-ii

 /*
	 * Runtime: 9 ms. Your runtime beats 93.99 % of java submissions.
	 * 参考自leetcode网友：@ChengZhang
	 * The main idea is based on greedy. Let's say the range of the current jump
	 * is [curBegin, curEnd], curFarthest is the farthest point that all points
	 * in [curBegin, curEnd] can reach. Once the current point reaches curEnd,
	 * then trigger another jump, and set the new curEnd with curFarthest, then
	 * keep the above steps, as the following
	 */
	public int jump(int[] A) {
		int jumps = 0, curEnd = 0, curFarthest = 0;
		for (int i = 0; i < A.length - 1; i++) {
			curFarthest = Math.max(curFarthest, i + A[i]);
			if (i == curEnd) {
				jumps++;
				curEnd = curFarthest;
			}
		}
		return jumps;
	}

• 贪心解法：参考：http://blog.sina.com.cn/s/blog_6a0e04380102v5ag.html
• 贪心大法好，但真的难想明白。。首先，要设置三个值：当前位置（是一个区域：从i~furthest_pre中，区域中的点中能到达的最大位置）所能到达的最大位置（furthest_cur)，当前位置的上一个位置(也是区域）所能到达的最大位置（furthest_pre），还有就是所走的步数。
• 有一点可能有点会懵，furthest_cur是还没有step++的时候，具体结合代码，也就是是一个预判能走到的但还没走的状态。
• 感觉讲的还是有点乱，现在抛开代码，想象我们站在题目给的数组的开头位置：从开始位置到开始位置能走到的最大距离（furthest_pre）之间构成了一块区域，然后我们开始一格一格走，每走一下刷新一下当前这块区域能到的最大位置(furthest_cur)，如果走到从开始位置走到了furthest_pre那我们也刷新出了最大的furthest_cur,如果furthest_cur比终点大，那恭喜！再跳一不就到终点了！可以开始跳一步咯！然后重复上述的动作，直到到达终点。
• 如果能一步到最大位置furthest_pre，那肯定能到一步到它前面那块区域的某一位置，实行下一步跳，跳到furthest_cur。
• 给一个测试用例，可以在纸上画画：

4 1 6 9 7 4 5 0 6 8 1 2 3 5 8 0 2 1 2

代码

public class Solution {
    public int jump(int[] A) {
        int len=A.length;
        if(len==0||A==null){
            return 0;
        }
        int furthest_cur=0;
        int furthest_pre=0;
        int steps=0;
        for(int i=0;i<len;i++){
            if(furthest_pre>=len){
                return steps;
            }
            if(i>furthest_pre){
                furthest_pre=furthest_cur;
                steps++;
            }
            furthest_cur=Math.max(furthest_cur,A[i]+i);
        }
        return steps;
    }
}

class Solution {
public:
    // 当前能够到达的最远距离还没有到n，必须再走下一步
    int jump(int A[], int n) 
    {
        int curReach=0,maxReach = 0,steps=0;
        for(int i=0;i<n && i<=maxReach;i++)
        { 
            if(i>curReach)    //steps-1步能够到达的距离,必须再走一步了
            {
                ++steps;
                curReach = maxReach;
            } 
            maxReach = max(maxReach,i+A[i]); // step步最远距离
        }
        if(maxReach<n-1)
            return -1;
        else
            return steps;
    }
};

class Solution {
public:
    int jump(int A[], int n) {
        int cur=0;  // 每个台阶内最远去的地方
        int last=0;  // 每一步直接能跨越的最远距离
        int step=0;  //步数
        for(int i=0; i<n && cur>=i; ++i)
        {
            if(i>last)
            {
                last=cur;
                step++; 
            }
            cur =max(cur, A[i]+i);
        }
        
        return step;
        
    }
};

/*
 贪心算法可以解决, 关键是三个变量的含义
 cur_step_max_point  使用当前的步数可以去的最远位置
 next_step_max_point 使用当前的步数，如果再走一步，可以到达的最远位置
 step 当前的步数
 -------------------
 一个具体的例子，i=1讲得比较详细，后面的基本就是代码流程。
 A[7] =  {3, 1, 2, 1, 2, 3, 2}
 初始状态：此时step=0, 所以最远能去0, 下一步能去的最远位置就是A[0]
 i = 0: 就是初试状态，step = 0， cur_step_max_point = 0, next_step_max_point = A[i] = 3;
 i = 1: 此时已经超过了当前步数step=0的的极限了，所以迈出一步，step = 1，同时当前步数可以到的最远点位置
        就要更新了，即cur_step_max_point = next_step_max_point = 3;同时next_step_max_point也
        可以更新了，即A[i] + i, 此时A[i] + i值为2，还不如i = 0时的next_step_max_point大，所以不更
        新，因为去2这个位置当前步数1就满足。
 i = 2  此时cur_step_max_point = 3，在当前步数的射程范围内，不用新增步数。但是在i = 2位置，下一步可以
        去的最远位置要更新了，因为A[i] + i = 4， 大于之前存的下一步可以到达的最远位置。next_step_max_point = 4;
 i = 3  也在cur_step_max_point = 3的射程范围内, cur_step_...不更新。此时i=3下一步能到达的最远位置A[3]+1=4,
        也不用更新
 i = 4  此时i已经超出了step = 1所能到达的最远距离cur_step... = 3。所以step++，step = 2。更新cur_step_...，令
        cur_step_max_point = next_step_max_point = 4。同时更新next_step_max_point = A[i] + i = 6;
 i = 5  此时i又超过了step = 2时的最大位置cur_step_max_point = 4。所以step++，step = 3
        cur_step_max_point = next_step_max_point = 6。next_step_max_point = A[i] + i = 8;
 
 这是突然发现cur_step_max_point = 6. 大于等于n。说明当前步数可以到达n点，于是直接return step.
 */
int jump(int A[], int n)
{
    if (n == 1 || n == 0) return 0;
    
    int next_step_max_point = A[0];  //下一步可以到达的最远距离
    int cur_step_max_point = 0;      //当前步数可以去的最远距离
    int step = 0;                    //去next_step_max_point的累计步数
    
    for(int i = 0; i < n; i++)
    {
        if (i > cur_step_max_point)
        {
            cur_step_max_point = next_step_max_point;
            step++;
        }
        if (cur_step_max_point >= n)
        {
            return step;
        }
        next_step_max_point = max(A[i] + i, next_step_max_point);
    }
    return step;
}

public class Solution {
public int jump(int[] A) {
 int len = A.length;
 int[] dp = new int[len];
 for(int i=1;i<len;i++){
 for(int j=1;j<=i;j++){
 if(i-(i-j)<=A[i-j]){
 dp[i]=dp[i-j]+1;
 }
 }
 }
 return dp[len - 1];
 }
 }

    /*
    * 目的：用最少的跳跃次数来到达数组的最后一个元素的位置
    * 方法：动态规划
    */
    int jump(int A[], int n) {
        vector<int>dp(n,INT_MAX);
        dp[0] = 0;
        for (int i = 0; i<n;i++){
            int maxp = min(i+A[i],n-1);
            for (int j = i+1;j<=maxp;++j){
                dp[j] = min(dp[j],dp[i]+1);
            }
        }
        return dp[n-1];
    }

class Solution {
public:
    int jump(int A[], int n) {
        if(n==1) return 0;
        if(n==2) return 1;
        int a[n-1];
        a[0] = 1;
        int i,j;
        for(i=1;i<=n-2;i++){
            if(A[n-2-i]>=i+1)
                a[i] = 1;
            else{
                a[i] = n;
                for(j=1;j<=A[n-2-i];j++){
                    if(1+a[i-j]<a[i])
                        a[i] = 1+a[i-j];
                }
            }
        }
        return a[n-2];
    }
};

先预处理一遍，把第i个为能走到的最大坐标存起来。 
我们从后往前处理，每次找到第一个能够大于等于目标值的坐标， 
把找到的坐标更新为下一个目标值，一直找到目标值为起始位置坐标，即为最小步数。
public int jump(int[] A) {
        int[] b=new int[A.length];
        for (int i = 0; i < A.length; i++) {
            b[i]=i+A[i];
        }
        int ans=0;
        int end=A.length-1;
        while (true){
            for (int j = 0; j < end; j++) {
                if(b[j]>=end){
                    end=b[j]-A[j];
                    ++ans;
                    break;
                }
            }
            if(end==0){
                break;
            }
        }
        return ans;
    }

//动态规划
public class Solution {
    public int jump(int[] A) {
        int[] dp = new int[A.length + 1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i < A.length; i++) {
            int index = A[i - 1] + i ;
            while ( index > i) {
                if (index < dp.length &&dp[i] + 1 < dp[index])
                    dp[index] = dp[i] + 1;
                index--;
            }
        }
        return dp[A.length];
    }
}

class Solution {
public:
    int jump(int A[],int n) {
          int last=0,r=0,ans=0;
          for(int i=0;i<n&&i<=r;i++){
              if(i>last){
                 last=r;
                 ans++; 
              }
              r=max(r,i+A[i]);
          }
          return r>=n-1?ans:-1;
    }
};

class Solution {
public:
    int jump(int A[], int n) {
        int *dp = new int[n]();  // dp存放都到各点的最小步数
        for(int i = 0; i < n; i++)
        {
            int maxp = min(i+A[i],n-1);  // 从i 出发能走到的最远距离
            for (int j = i + 1; j <= maxp; j ++) {
                if(dp[j] == 0 || dp[j] > dp[i]+1) 
                    dp[j] = dp[i] + 1; 
                 // 如果位置没被走过,或者可以用更少步数到达，则到达j点的步数为dp[i]+1
            }
        }
        int res = dp[n-1];
        delete [] dp; 
        dp = nullptr;
        return res;
    }
};

/*
用一个标号数组存储每个点到终点的最短距离，初始设置终点的dis为0；
从后往前更新每个点的最短距离即可
*/
class Solution {
public:
    int jump(int A[], int n) {
        if(n==0)return 0;
        int maxnum = 0xffffff;
        int dis[10000];
        for (int i = 0; i < sizeof(dis) / sizeof(dis[0]); i++)dis[i] = maxnum;
        dis[n-1]=0;
        for(int i=n-2;i>=0;i--){
            if(A[i]+i>=n-1)dis[i]=1;
            else for(int j=i;j<=A[i]+i;j++)if(dis[i]>dis[j]+1)dis[i]=dis[j]+1;
        }
        if(dis[0]==maxnum)return -1;
        return dis[0];
    }
};

public class Solution {
    public int jump(int[] A) {
        if(A.length==0){
            return 0;
        }
        int furstep = 0,furpre = 0,step = 0;
        for(int i = 0;i<A.length;i++){
            if(furpre>=A.length-1){
                return step;
            }
            if(i>furpre){
                furpre = furstep;
                step++;
            }
            furstep = Math.max(furstep,A[i] + i);
        }
        return step;
    }
}

public class Solution {
    public int jump(int[] A) {
        if(A == null || A.length <= 0)
        	return -1;
        // 动态规划，dp[i]放置到达i点的最少步数    
        int[] dp = new int[A.length];
        // 首先都赋值max
        for(int i = 0; i < A.length; i++)
        	dp[i] = Integer.MAX_VALUE;
        
        dp[0] = 0;
        for(int i = 0; i < A.length; i++){
              // A[i]>0，说明此点可达
        	if(A[i] > 0){
        		for(int j = 1; j <= A[i]; j++){
        			if(i + j < A.length)
        				dp[i + j] = Math.min(dp[i] + 1, dp[i + j]);
               // 第一次到达终点直接返回
                    if(i + j == A.length - 1)
        				return dp[A.length - 1];
            	}
        	}       	
        }        
        return dp[A.length - 1];
    }
}

public class Solution {
    public int jump(int[] A) {
          if(A.length==1)
        return 0;
           int minstep=1,minindex=A[0],maxindex=minindex;
     for(int i=1,length=A.length;i<length;i++){
    if(i>minindex){
     minstep++;
    minindex=maxindex;
     }
    if(A[i]+i>maxindex){
maxindex=A[i]+i;
   }
   }
   return minstep;
        
    }
}

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];
	}

符合动态规划的条件：

1. 每个状态与前一个状态有关——设到i的最少步数为f(i)，则f(i) = f(i的上一个点) + 1
2. 初始状态是已知的——刚开始几个点的f与第一个点有关

然后就是实现问题了，两个循环，外循环是遍历每个点，内循环是遍历当前点的“势力范围”。

class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @return int整型
     */
    int jump(int *A, int n) {
        // write code here
        // 动态规划：设到i的最少步数为f(i)，则f(i) = f(i的上一个点) + 1
        // dp数组保存到第i个点最少的步数
        if (n <= 1) return 0;
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            int maxIdx = min(A[i] + i, n - 1);  // 从i走能到的最大位置
            for (int j = i + 1; j <= maxIdx; ++j) {
                if (dp[j] == 0) dp[j] = dp[i] + 1; // 位置没有被走过，保存最小步数
            }
            if (dp[n - 1] != 0) return dp[n - 1];
        }
        return -1;
    }
};