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

题目

在这里插入图片描述


解题思路

1.带备忘录的递归(会超时)

以示例画图分析如下:
在这里插入图片描述
代码如下:


 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到最大跳跃步数  递归分解不到最后

           

2.贪心算法

在这里插入图片描述

代码如下:

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      

版权声明:本文为yousurelyx原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。