当前位置：首页 > news >正文

跳跃游戏 dp还是线段树优化

news 2025/6/8 9:40:54

题目地址

在这里插入图片描述

这个题目还是比较经典的，题目给的数据量如果是动态规划的思路来写的话刚刚好能过

代码如下：

class Solution:def jump(self, nums: List[int]) -> int:n = len(nums)dp = [inf]*(n)dp[0] = 0for i in range(n):if dp[i] == inf:continuefor j in range(1,nums[i]+1):if i+j>=n:continuedp[i+j] = min(dp[i+j],dp[i]+1)return dp[n-1]

如果数据量变大咋办，感觉可以用线段树来优化一下

from math import infclass Tree:def __init__(self, n):self.n = nself.t = [inf] * (4 * n)  # 存储区间最小值self.lazy = [None] * (4 * n)  # 懒标记，初始为None表示没有待下推的值def push_down(self, o):if self.lazy[o] is not None:# 下推懒标记到左右子节点left = o * 2right = o * 2 + 1# 更新左子节点self.t[left] = min(self.t[left], self.lazy[o])self.lazy[left] = min(self.lazy[left], self.lazy[o]) if self.lazy[left] is not None else self.lazy[o]# 更新右子节点self.t[right] = min(self.t[right], self.lazy[o])self.lazy[right] = min(self.lazy[right], self.lazy[o]) if self.lazy[right] is not None else self.lazy[o]# 清除当前节点的懒标记self.lazy[o] = Nonedef update(self, o, l, r, L, R, va):if L <= l and r <= R:# 完全包含，更新当前节点并设置懒标记self.t[o] = min(self.t[o], va)self.lazy[o] = min(self.lazy[o], va) if self.lazy[o] is not None else vareturn # 下推懒标记self.push_down(o)mid = (l + r) // 2if mid >= L:self.update(o * 2, l, mid, L, R, va)if mid < R:self.update(o * 2 + 1, mid + 1, r, L, R, va)# 更新当前节点的值self.t[o] = min(self.t[o * 2], self.t[o * 2 + 1])def query(self, o, l, r, L, R):if L <= l and r <= R:return self.t[o]# 下推懒标记self.push_down(o)tmp = infmid = (l + r) // 2if mid >= L:tmp = min(tmp, self.query(o * 2, l, mid, L, R))if mid < R:tmp = min(tmp, self.query(o * 2 + 1, mid + 1, r, L, R))return tmp         class Solution:def jump(self, nums: List[int]) -> int:n = len(nums)a = Tree(n)a.update(1,0,n-1,0,0,0)for i in range(n):now = a.query(1,0,n-1,i,i)if now == inf:continuea.update(1,0,n-1,i,min(i+nums[i],n-1),now+1)return a.query(1,0,n-1,n-1,n-1)

如果数据量更大呢，题目保证了一定可以到达n-1，所以我们就可以采取贪心的思路

class Solution:def jump(self, nums: List[int]) -> int:ans = 0cur_right = 0  # 已建造的桥的右端点next_right = 0  # 下一座桥的右端点的最大值for i in range(len(nums) - 1):# 遍历的过程中，记录下一座桥的最远点next_right = max(next_right, i + nums[i])if i == cur_right:  # 无路可走，必须建桥cur_right = next_right  # 建桥后，最远可以到达 next_rightans += 1return ans

怎么理解呢
在这里插入图片描述