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

题目地址

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

代码如下：

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

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

from math import inf

class Tree:
    def __init__(self, n):
        self.n = n
        self.t = [inf] * (4 * n)  # 存储区间最小值
        self.lazy = [None] * (4 * n)  # 懒标记，初始为None表示没有待下推的值
    
    def push_down(self, o):
        if self.lazy[o] is not None:
            # 下推懒标记到左右子节点
            left = o * 2
            right = 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] = None

    def 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 va
            return 
        
        # 下推懒标记
        self.push_down(o)
        
        mid = (l + r) // 2
        if 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 = inf
        mid = (l + r) // 2
        if 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:
                continue
            a.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 = 0
        cur_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_right
                ans += 1
        return ans

怎么理解呢