Question: https://oj.leetcode.com/problems/jump-game-ii/
Question Name: Jump Game II
A similar problem with Fib-Frog by codility. But this one is much simpler.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution: # @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 = [0] * 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 return steps[-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.