Check comments in the code.
def jump2(self, A): """ Basically it's a shortest-path problem. As an unweighted graph, BFS should be able to solve it in O(|E|). But as it's an array with non-negative numbers, we can't jump backward. So we can do better here. Suppose we devided the arrays into segments depending on the elment in the array. So for each segment, we find the farthest index we can jump. For example, the first segment is always A. The second will be from A to A[A]. The third will be from A[A] to the farthest index we can find in the second segment. We start looking between the end of the last segment and the begin of the next segment. """ ans = lastIdx = nextIdx = 0 while nextIdx < len(A) - 1: ans += 1 lastIdx, nextIdx = nextIdx, max(i + A[i] for i in xrange(lastIdx, nextIdx + 1)) return ans
def jump(nums): return 1 if len(nums) - 1 <= nums else 1 + self.jump(nums[max([(i + nums[i], i) for i in xrange(nums + 1)]):])
Think you for your code! Here is my question: I think the thought is similar to yours, but mine got an MLE. Is it recursion's fault?
There's a stack limit in Python, which is by default 256 and has been hit pretty hard by your code.
Check this case:  * 100000
Yes, I got an MLE just because of it. Is the stack limit the limit of recursion? Could you give me some suggestions that I improve it? Thank you!
yep. your recursion is too deep. I suggest using iteration instead of recursion to get rid of the limit.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.