原题
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
给出数组A =** [2,3,1,1,4]**，最少到达数组最后一个位置的跳跃次数是2(从数组下标0跳一步到数组下标1，然后跳3步到数组的最后一个位置，一共跳跃2次)
解题思路
- 方法一：贪心(Greedy)
- 维护一个
farthest变量，每次在遍历start到end之间的元素，尝试更新farthest变量 start = end + 1end = farthest- 比较
end时候大于数组长度，大于返回结果，否则steps += 1 - 方法二：动态规划(领会思路，OJ会超时)
- �开辟一个
steps数组长度与input数组相同，初始值为maxint steps[0] = 0-
steps[i]等于遍历steps[0]~steps[i-1]，如果存在nums[x] + x > i，则更新steps[i] = steps[x] + 1
完整代码
# 方法一：贪心
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return -1
start, end, steps = 0, 0, 0
while end < len(nums) - 1:
steps += 1
farthest = end
for i in range(start, end + 1):
if nums[i] + i > farthest:
farthest = nums[i] + i
start = end + 1
end = farthest
return steps
# 方法二：动态规划
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
steps = [sys.maxint for i in range(len(nums))]
steps[0] = 0
for i in range(1, len(nums)):
for j in range(i):
if steps[j] != sys.maxint and j + nums[j] >= i:
steps[i] = steps[j] + 1
break
return steps[len(nums) - 1]
