按关键词阅读：
文章插图
力扣杯 LCP 09. 最小跳跃次数「链接」（点击查看题目)
题目描述
为了给刷题的同学一些奖励 ， 力扣团队引入了一个弹簧游戏机 。 游戏机由 N 个特殊弹簧排成一排 ， 编号为 0 到 N-1 。 初始有一个小球在编号 0 的弹簧处 。 若小球在编号为 i 的弹簧处 ， 通过按动弹簧 ， 可以选择把小球向右弹射 jump[i] 的距离 ， 或者向左弹射到任意左侧弹簧的位置 。 也就是说 ， 在编号为 i 弹簧处按动弹簧 ， 小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N， 则表示小球弹出了机器） 。 小球位于编号 0 处的弹簧时不能再向左弹 。
为了获得奖励 ， 你需要将小球弹出机器 。 请求出最少需要按动多少次弹簧 ， 可以将小球从编号 0 弹簧弹出整个机器 ， 即向右越过编号 N-1 的弹簧 。
【LeetCode 题解 | 力扣杯 LCP 09.最小跳跃次数】示例 1：
输入：jump = [2, 5, 1, 1, 1, 1]
输出：3
解释：小 Z 最少需要按动 3 次弹簧 ， 小球依次到达的顺序为 0 -> 2 -> 1 -> 6 ， 最终小球弹出了机器 。
限制：
- 1 <= jump.length <= 10^6
- 1 <= jump[i] <= 10000
题意概述给定一个数组 jump ， 长度为 N ， 在第 i 个位置可以选择跳到 0..i-1 和 i + jump[i] ， 问从 0 跳过 n-1的最小跳跃次数是多少 。
方法一：动态规划我们可以利用一个巧妙的性质来使用动态规划：假设某一个位置只需要 w 步可以跳到 ， 那么这个位置之前的步数 ， 最多只需要 w+1 步 。
所以我们可以用一个数组 maxdis[w] 表示 w 步可以跳到的最远位置 。 对于位置 i 而言 ， 满足 maxdis[w] > i条件的最小 w+1 是往左跳到达 i 的最小操作次数 。
因此递推方程为
- f[i] = min(f[i], w+1): 用往左跳到达 i 的最小操作数 w+1
- f[i+jump[i]] = min(f[i+jump[i],f[i]+1): 从 i 往右跳到 i+jump[i] 更新 f[i+jump[i]]
- maxdis[f[i+jump[i]]] = max(maxdis[f[i+jump[i]]], i+jump[i]):更新 f[i+jump[i]] 次操作到达最远距离 。
C++ 实现
class Solution {private:int f[10000000 + 7];int maxdis[10000000 + 7];public:int minJump(vectorint w = 0;int ans = 1000000000;for (int i=1; i<=n; ++i) {f[i] = 1000000000;maxdis[i] = 0;}f[1] = 0;maxdis[0] = 1;for (int i=1; i<=n; ++i) {if (i > maxdis[w]) { // 更新单调指针++w;}f[i] = min(f[i], w+1); // 用 maxdis[w] 更新 f[i]int next = i + jump[i-1]; // 第一步跳跃更新if (next > n) {ans = min(ans, f[i] + 1);} else if (f[next] > f[i] + 1) {f[next] = f[i] + 1;maxdis[f[next]] = max(maxdis[f[next]], next);}}return ans;}}; Python 实现class Solution:def minJump(self, jump: List[int]) -> int:res = n = len(jump)f = [n]*(n+1)f[0] = 0max_dis = [0]*(n+1)curr_min_num = 0for i in range(0,n):if i>max_dis[curr_min_num]:curr_min_num += 1f[i] = min(f[i],curr_min_num+1)jump_tmp = i+jump[i]if jump_tmp>=n:res = min(res,f[i]+1)else:f[jump_tmp] = min(f[jump_tmp],f[i]+1)max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)return resGo 实现func minJump(jump []int) int {n := len(jump)res := len(jump)var f[1000001]intvar max_dis[1000001]intfor i:=0; i<=n; i++{f[i] = n+1;max_dis[i] = 0;}f[0] = 0curr_min_num := 0for i:=0; imax_dis[curr_min_num]{curr_min_num += 1}f[i] = Min(f[i], curr_min_num+1)jump_tmp := i+jump[i]if jump_tmp>=n {res = Min(res,f[i]+1)}else{f[jump_tmp] = Min(f[jump_tmp],f[i]+1)max_dis[f[i]+1] = Max(max_dis[f[i]+1],jump_tmp)}}return res}func Min(x, y int) int {if x < y {return x}return y} func Max(x, y int) int {if x > y {return x}return y} 复杂度分析时间复杂度：O(n) 。
空间复杂度：O(n) 。
方法二：广度优先搜索常规广度优先搜索在处理弹簧往左跳的情况时 ， 时间复杂度到达 O(N^2) 。
在常规广度优先搜索的基础上 ， 我们可以记录一个最大的 far 值进行优化 ， 用来表示当前从 [0, far-1] 均已被搜索到 。
因此当搜索到编号 i 弹簧时 ， 往左跳的操作 ， 仅需遍历 [far, i-1] 区间（ far <= i-1 ）；搜索结束时 ， 更新 far = max(far, i+1) 。
由于 far 的更新操作 ， 使往左跳操作的遍历区间是不存在重复的 ， 因此往左跳遍历的总时间复杂度为 O(N)
Python 实现
class Solution:def minJump(self, jump):res = n = len(jump)visited = [False]*(n+1)queue = [[0,1]]visited[0] = Truecurr, far = 0, 1while curr= n:return stepif not visited[idx+jump[idx]]:queue.append([idx+jump[idx], step+1])visited[idx+jump[idx]] = Truefor j in range(far, idx):if not visited[j]:queue.append([j, step+1])visited[j] = Truefar = max(far, idx+1)return -1
稿源：(未知)
【傻大方】网址：http://www.shadafang.com/c/111J2T552020.html
标题：LeetCode 题解 | 力扣杯 LCP 09.最小跳跃次数