企业官网建设流程全解析

LeetCode LCP 09. 最小跳跃次数 — Java 实现

题目概述

有 `N` 个弹簧排成一排（编号 `0` 到 `N-1`），小球初始在编号 `0` 处。在编号 `i` 的弹簧处，可以：
- 向右弹射 `jump[i]` 的距离到 `i + jump[i]`（若超出边界则弹出机器）
- 向左弹射到任意左侧弹簧 `0` 到 `i-1`

求将小球弹出机器的最少按动次数。

---

解题思路：反向 DP

设 `dp[i]` 为从位置 `i` 弹出机器的最小次数。

从后往前遍历，对于位置 `i`：

1. 直接向右跳：`dp[i] = (i + jump[i] >= n) ? 1 : dp[i + jump[i]] + 1`
2. 利用左侧跳转优化右侧：由于从任意右侧位置 `j (> i)` 都可以向左一步跳到 `i`，所以如果 `dp[j] >= dp[i] + 1`，则更新 `dp[j] = dp[i] + 1`。

当遇到 `dp[j] < dp[i] + 1` 时即可 `break`，因为更左侧的位置已经被更优地更新过了。

这个 `break` 剪枝使得均摊时间复杂度接近 O(N)。

---

Java 代码

```java
class Solution {
public int minJump(int[] jump) {
int n = jump.length;
// dp[i] 表示从位置 i 弹出机器的最小次数
// 初始化为一个较大值，这里用 n + 1 足够（最多 n 步一定能出去）
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = n + 1;
}

// 从后往前遍历
for (int i = n - 1; i >= 0; i--) {
// 情况1：直接向右跳
if (i + jump[i] >= n) {
dp[i] = 1;
} else {
dp[i] = dp[i + jump[i]] + 1;
}

// 情况2：从右侧位置 j 向左跳到 i，再从 i 出去
// 如果 dp[j] 可以通过先跳到 i 变得更优，则更新
for (int j = i + 1; j < n && dp[j] >= dp[i] + 1; j++) {
dp[j] = dp[i] + 1;
}
}

return dp[0];
}
}
```

---

复杂度分析

项目 复杂度 说明
时间 O(N) 均摊线性，每个位置最多被更新常数次
空间 O(N) dp 数组

---

示例验证

输入：`jump = [2, 5, 1, 1, 1, 1]`

i jump[i] 直接向右 dp[i] 初始 优化右侧后 最终 dp[i]
5 1 5+1=6≥6 → 1 1 — 1
4 1 4+1=5<6 → dp[5]+1=2 2 dp[5]=1 < 3, break 2
3 1 3+1=4<6 → dp[4]+1=3 3 dp[4]=2 < 4, break 3
2 1 2+1=3<6 → dp[3]+1=4 4 dp[3]=3 < 5, break 3
1 5 1+5=6≥6 → 1 1 dp[2]=3≥2 → 2; dp[3]=3≥2 → 2; dp[4]=2≥2 → 2; dp[5]=1<2 break 1
0 2 0+2=2<6 → dp[2]+1=3 3 dp[1]=1<4, break 3

输出：`3` ✓（路径：0 → 2 → 1 → 弹出）