def jump(self, A): if len(A) == 1: return 0 i = 0 result = 0 while i < len(A): if A[i] + i >= len(A)-1: return result + 1 max_inc = 0 max_j = 0 for j in xrange(A[i]): inc = A[i+j+1] + j + 1 if inc > max_inc: max_inc = inc max_j = j+1 i = i+max_j result += 1
The key is to calculate the maximum jump length every time. This is the core concept of greedy algorithm.
But how to calculate that? Suppose you are positioned at index n . A[n] is the maximum length you can jump. However, this number may not be the length you want. Because you may get 1 after jumping the maximum length and get 100 after jumping only 1 length. So what you should calculate is the maximum of sum of A[n+k] and k . And k is the length you want