leetcode 45 跳跃游戏2
贪心的方法，从后往前找到哪些值可以跳到终点，取离终点最远的点，然后在接着找哪些点可以到这个点，那个点离这个点最远。注意从一个点到另一个点是算一步。
通过一步一步的局部最优，达到全局最优。
end=len(nums)
count=0
while end!=1:
for i in range(end):
if nums[i]+i>=end-1:
print(end-1-i)
count+=1
end=i+1
break
return count 通过递归方法，模拟选择的过程，然后通过递归回来将每一步加在count上面，同时比较得出最小值。
这里因为超时，需要记忆化递归
class Solution:
def jump(self, nums: List[int]) -> int:
memo={}
def dfs(i):
if i==len(nums)-1:
return 0
if i>len(nums)-1:
return -1
mini=float('inf')
for j in range(1,nums[i]+1):
if i+j in memo:
res=memo[i+j]
else:
res=dfs(i+j)
memo[i+j]=res
if res>=0 and res<mini:
mini=res+1
return mini
return dfs(0)使用lru_cache 参数填None
@functools.lru_cache(maxsize=None, typed=False)
参数是要存多少数据
使用 functools 模块的 lur_cache 装饰器，可以缓存最多 maxsize 个此函数的调用结果，从而提高程序执行的效率，特别适合于耗时的函数。参数 maxsize 为最多缓存的次数，如果为 None，则无限制，设置为 2 的幂 时，性能最佳；如果 typed=True（注意，在 functools32 中没有此参数），则不同参数类型的调用将分别缓存，例如 f(3) 和 f(3.0)。
class Solution:
def jump(self, nums: List[int]) -> int:
memo={}
@functools.lru_cache(None)
def dfs(i):
if i==len(nums)-1:
return 0
if i>len(nums)-1:
return -1
mini=float('inf')
for j in range(1,nums[i]+1):
res=dfs(i+j)
if res>=0 and res<mini:
mini=res+1
return mini
return dfs(0)
count=0正面寻找每次可以找到可以到达的最远位置的位置，通过一次for循环，当当前i遍历到最远边界的时候，次数增加一。
由于在下标为0的位置增加了一次1,所以只遍历到len(nums)-1
count=0
maxpos=0
end=0
for i in range(len(nums)-1):
maxpos=max(maxpos,nums[i]+i)
if i==end:
count+=1
end=maxpos
return count
