LCP 09. 最小跳跃次数

https://leetcode-cn.com/problems/zui-xiao-tiao-yue-ci-shu/

我最开始的想法是BFS，但是很快枪毙了，是因为如果考虑向前跳的话，那么可能会出现O(n^2)的算法。但实际情况是，如果按照深度顺序去更新的话，并不是每次都需要考虑所有的前面节点，只需要考虑到上次更新之后的节点。下面代码参考的是这个解答

class Solution:
    def minJump(self, jump: List[int]) -> int:
        n = len(jump)
        depth = [0] * n

        from collections import deque
        dq = deque()
        dq.append(0)
        max_left = 0
        ans = 0

        while dq:
            x = dq.popleft()
            y = x + jump[x]
            if y >= n:
                ans = depth[x] + 1
                break

            if not depth[y]:
                depth[y] = depth[x] + 1
                dq.append(y)

            for y in range(max_left + 1, x):
                if not depth[y]:
                    depth[y] = depth[x] + 1
                    dq.append(y)
            max_left = max(max_left, x)

        return ans

实际上这里还有更牛的回答：一种经典的套路，我忍不住摘抄过来

直接建图跑最短路复杂度是O(n^2)的，因为对每个u>v，都有一条从u到v的边。一种经典的套路就是对每个u新增对应虚拟点u'，然后新增三种边：
1.每个u向u'连一条边，长度为1。
2.每个u'向(u-1)'连一条边，长度为0。
3.每个u'向u连一条边，长度为0。
那么就等效于对每个u>v，都有一条长度为1的路径。