Question Name: Jump Game II
A similar problem with Fib-Frog by codility. But this one is much simpler.
Solution to Jump Game II by LeetCode
# @param A, a list of integers
# @return an integer
def jump(self, A):
# steps[i] means the minimum number of jumps needed to reach the position i.
steps =  * len(A)
for index in xrange(len(A)):
preSteps = steps[index] # Minimum jumps needing to reach position index
step = A[index] # Maximum jump length at position index
# Try to jump with steps of "step" to 1
for jump in xrange(step, 0, -1):
if index + jump >= len(steps): continue # Out of range
if steps[index + jump] != 0: break # Reached before
steps[index + jump] = preSteps + 1
Your solution is O(N^2) in the worst case? [1,5,4,3,2,1,1,1]
Yes, I think so. The time complexity of my solution is much worse than yours.