LeetCode 55.跳跃游戏 python 递归和贪心

• 题目
• 解题思路
• • 1.带备忘录的递归（会超时）
  • 2.贪心算法

以示例画图分析如下：

代码如下：

 class Solution:
     def canJump(self, nums: List[int]) -> bool:
         if nums is None:
             return True
         self.total_index=len(nums)
         self.end_index=self.total_index-1

         self.memo=dict()    # 开启备忘录 把需要重复计算的步骤 只计算一遍 下次遇到直接字典里去取
         return self.dfs(0,nums)

     def dfs(self,index,nums):
         if index>=self.end_index:   # 结束条件  eg：f(4)中的4 等于end_index    f(3)中的3 小于end_index
             return True
         if index in self.memo:      # 若之前计算过，则直接返回之前的计算结果
             return self.memo[index]
         for i in range(1,nums[index]+1):  # 某个位置上，跳跃步数的选择  从1开始 到最大
             if self.dfs(index+i,nums):    # 递归  关系式 f(n)--->f(n+1)、f(n+2)....f(n+nums[index])
                 self.memo[index]=True
                 return True
         self.memo[index]=False
         return False   # 从1到最大跳跃步数  递归分解不到最后

           

代码如下：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
       total_index=len(nums)
       end_index=total_index-1
    
       max_distance=nums[0]
       for i in range(total_index):
           
           if i<=max_distance:    # 可达
               max_distance=max(max_distance,i+nums[i])  # 更新最远距离
           
               if max_distance>=end_index: 
                   return True
       return False