Leetcode 55. 跳跃游戏

心路历程：

这道题给我留下了很深的印象，因为一开始用回溯写的，但是搞了半天没搞出来。
回溯的核心思维其实是遍历所有并且记录路径path，并且当子状态无法返回父状态时，是不需要记录visited的，只需要记录path。
回溯的核心是回溯路径也就是path。

后来发现这道题其实是动态规划问题，典型的从子问题可以推到父问题，但是需要注意这道题对于时间和空间复杂度的要求是比较高的，从这也能看出来这道题其实也是个贪心问题。

注意的点：

1、回溯法的核心是回溯path也就是路径
2、注意区分数组长度和数组的索引，尤其是用[]*len方法时
3、可以用当前状态+候选集的方式构建树来统一分析dp和回溯问题
4、在一些问题上，nonlocal声明是必不可少的，尤其是当变量为非类对象时，比如res=int,bool等具有实际内存的变量，必须要在递归函数中声明nonlocal res；否则只能使用不能赋值。因为列表是个类，所以可省略声明。

解法一：递归动态规划：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        @cache
        def dp(i): # 表示从第i个位置开始能否跳到最后一个下标
            if i == len(nums) -1: return True
            if i > len(nums) - 1: return False

            for k in range(1, nums[i]+1):
                if dp(i+k):
                    return True
            return False
        return dp(0)

解法二：数组动态规划：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dp = [False] * len(nums)
        dp[-1] = True
        for i in range(len(nums)-2, -1, -1):
            for k in range(1, nums[i]+1):
                if i + k <= len(nums) - 1 and dp[k+i]:
                    dp[i] = True
                    break
        return dp[0]            

超时解法：回溯：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 对于回溯问题，如果递归的方向不涉及上一个位置的话，只用for循环遍历candicate是不需要记录visited
        path = []
        res = False
        def dfs(i):
            nonlocal res   #必不可少的nonlocal
            # print(i)
            if i == len(nums) - 1: 
                if sum(path) == len(nums) - 1:
                    res = True
                    return
            if i > len(nums) - 1:
                return
            candicate = list(range(1, nums[i]+1))

            for each in candicate:
                path.append(each)
                # print(i, each, 'before')
                dfs(i+each)
                # print(i, each, 'after')
                path.pop()
        dfs(0)
        return res