Commit734aca2

committed

Lintcode/src/chapter4_DynamicProgrammingI/JumpGameII.java

1 parenta0ca774 commit734aca2Copy full SHA for 734aca2

File tree

+42

-0

lines changed

+42

-0

lines changed

Lines changed: 42 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,42 @@`
	`1`	`+packagechapter4_DynamicProgrammingI;`
	`2`	`+/**Given an array of non-negative integers, you are initially positioned at the first index of the array.`
	`3`	`+`
	`4`	`+Each element in the array represents your maximum jump length at that position.`
	`5`	`+`
	`6`	`+Your goal is to reach the last index in the minimum number of jumps.`
	`7`	`+`
	`8`	`+Example`
	`9`	`+Given array A = [2,3,1,1,4]`
	`10`	`+`
	`11`	`+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.)*/`
	`12`	`+publicclassJumpGameII {`
	`13`	`+`
	`14`	`+/**`
	`15`	`+ * @param A: A list of lists of integers`
	`16`	`+ * @return: An integer`
	`17`	`+ */`
	`18`	`+publicstaticintjump(int[]A) {`
	`19`	`+// write your code here`
	`20`	`+if(A ==null \|\|A.length ==0)return -1;`
	`21`	`+`
	`22`	`+int[]steps =newint[A.length];`
	`23`	`+steps[0] =0;`
	`24`	`+for(inti =1;i <A.length;i++)steps[i] =Integer.MAX_VALUE;`
	`25`	`+`
	`26`	`+for(inti =1;i <A.length;i++){`
	`27`	`+for(intj =0;j <i;j++){`
	`28`	`+if(steps[j] !=Integer.MAX_VALUE &&j +A[j] >=i){`
	`29`	`+steps[i] =steps[j]+1;`
	`30`	`+break;`
	`31`	`+ }`
	`32`	`+ }`
	`33`	`+ }`
	`34`	`+returnsteps[A.length-1];`
	`35`	`+ }`
	`36`	`+`
	`37`	`+publicstaticvoidmain(String...strings){`
	`38`	`+int[]A =newint[]{2,3,1,1,4};`
	`39`	`+System.out.println(jump(A));`
	`40`	`+ }`
	`41`	`+`
	`42`	`+}`

Comments

(0)