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.

Actually I got no trick for this problem, I just find forward, and see for each node of array, what is the current maximum place we can reach, and every time we reach a local maximum, we add counter by 1, if we can reach the terminal, just return the counter.

For example, A = `[2,3,1,1,4]`

At beginning, we set counter to be 0, during first counter cycle, we check A[0], which is 2, and so far we are able to reach A[0 + 2].

So during the second counter cycle, we check everything before the most far place we can reach, so let’s check A[1] and A[2], A[1] is 3, so we are now able to reach A[1 + 3], and it is the terminal, so we return 2.

Here is the code.

int jump(int A[], int n) { int start = 0; int end = 0; int count =0; if(n == 1) return 0; while(end < n) { int max = 0; count ++; for(int i = start; i <= end ; i ++ ){ if(A[i] + i >= n-1){ return count; } if(A[i] + i > max){ max = A[i] + i; } } start = end + 1; end = max; } }

:p

pipikaqiu

I strongly recommend you to add the complexity analysis to your algorithms.