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