 moonlightshadow123
6/25/2017 - 2:14 PM

## 45. Jump Game II

1. Jump Game II
``````# Time complexity: O(n)

class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return 0
n = len(nums)
reachIdx = nums
preReachIdx = 0
step = 1
while reachIdx < n-1:
newReachIdx = 0
for idx in range(preReachIdx+1, reachIdx+1):
newReachIdx = max(newReachIdx, nums[idx]+idx)
# New reachIdx = the max `nums[idx]+idx` from preReachIdx+1(including) to reachIdx(including),
# and then preReachIdx = old reachIdx.
# Note that [preReachIdx] is not included in the new reach idx evaluation.
step += 1
preReachIdx = reachIdx
reachIdx = newReachIdx

return step``````
``````# dp will encounter Time Limit Exceeded error for time complexity: O(n*avg(nums))

class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return 0

n = len(nums)
steps = [float('inf')] * n
steps[n-1] = 0
for curIdx in range(n-2,-1,-1):
varStart = curIdx + 1
varEnd = min(n-1, curIdx+nums[curIdx])
if varStart == varEnd+1:
continue
steps[curIdx] = min(steps[varStart:varEnd+1]) + 1
print steps
return steps``````

https://leetcode.com/problems/jump-game-ii/#/description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example: Given array A = `[2,3,1,1,4]`

The minimum number of jumps to reach the last index is `2`. (Jump `1` step from index 0 to 1, then `3` steps to the last index.)