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
原文地址:https://blog.csdn.net/weixin_43483381/article/details/137470438
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!