leetcode 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.

For example:
Given array A =?[2,3,1,1,4]

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.)

?這一題是自己做出來的。

首先考慮動態規劃的方法。定義一個數組distance[n] (n=A.length) distance[i]表示從A[0]移動到A[i]所需的最少步數。

初始化時，所有distance[i]都為postive limit。表示都不可達。

然后依次加入元素，第一輪循環從A[0]開始，表示從A[0]出發達到各個點的最小步數。

第二輪從A[1]開始，表示，從A[1]出發到達各個點的最小步數。

。。。。以此類推

則其狀態轉移方程為

if((j-i)<distance[i])//從i出發是否可以到達jif(distance[i]+1<distance[j])//這一路線是否比當前路線更優　
distance[j]=distance[i]+1

然而超時。

?

?

考慮了一下，該題的Tag中有Greedy。則開始考慮貪心的方法。

這個題目中，只要A[i]的值大于其步長，就可以跳到。因此，只要考慮這個條件即可。

不再考慮元素位置，而考慮步數。即，一步最遠可以跳到哪，兩步最遠可以跳到哪，以此類推，直到可以跳到終點。

以兩步為例

從A[0]出發最遠可以到達A[i]。則當0<k<i 時,A[k]都可以一步到達

因此，當情況為2步時，可以從1-i中中任意一點為出發點，計算其最遠可以到達的地方，假設為j。

當情況為3步時，只需計算從i，i+1,i+2....j出發，可以達到的最遠距離。

當最遠距離超過數組A的長度時，即返回步數。

下面給出代碼

?

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;public class Solution {/*** @param args*/ public int jump(int[] nums) {int end=nums[0];int path=1;int lastPoint=0;int next=nums[0];if(nums.length==1)return 0;while(true){if(next>=nums.length-1)return path;next=findMaxMid(nums,lastPoint,end);path++;lastPoint=end;end=next;//    System.out.println(lastPoint+"*"+end);
            }}public int findMaxMid(int []nums,int lastPoint,int end){int max=-1;int maxIndex=-1;for(int i=lastPoint;i<=end;i++){if(max<nums[i]+i){max=nums[i]+i;maxIndex=i;}}return max;}public static void print(int []nums){String result="{";for(int i:nums){result+=i+",";}System.out.println(result+"}");}public static void main(String[] args) {// TODO Auto-generated method stubint []a=new int[10000];for(int i=0;i<10000;i++){a[i]=1;}int []b={2,3,1,1,4};int []c=new int[25002];for(int i=25000;i>=1;i--){c[25000-i]=i;}c[25000]=1;c[25001]=0;//new Solution2().print(c);Scanner scanner=null;try {scanner=new Scanner(new File("D://data.txt"));} catch (FileNotFoundException e) {// TODO Auto-generated catch block
            e.printStackTrace();}int[] d=new int[30000];int i=0;while(scanner.hasNext()){String all=scanner.next();for(String as:all.split(",")){d[i]=Integer.parseInt(as);i++;}}for(int j=0;j<i;j++){c[j]=d[j];}print(c);System.out.println(new Solution().jump(c));}}

?