Greedy strategy. From left to right, for a stop at i, it choose next stop j as:
- j must reachable from i, which means j is from position [i+1, i+ A[i]] .
- A[j] should be the largest one
Namely, we choose the j that can help us reach as far as we can.
class Solution: # @param A, a list of integers # @return an integer def jump(self, A): if not A or len(A) == 1: return 0 cur = 0 count = 0 while(cur<len(A)): maxReach = -1 idx = 0 for i in range(1,A[cur]+1): if cur+i >= len(A)-1: return count+1 else: if A[cur+i] + i > maxReach: maxReach = A[cur+i] + i idx = cur+i cur = idx count +=1