LeetCode LCP 09. 最小跳跃次数 — Java 实现题目概述有 N 个弹簧排成一排编号 0 到 N-1小球初始在编号 0 处。在编号 i 的弹簧处可以- 向右弹射 jump[i] 的距离到 i jump[i]若超出边界则弹出机器- 向左弹射到任意左侧弹簧 0 到 i-1求将小球弹出机器的最少按动次数。---解题思路反向 DP设 dp[i] 为从位置 i 弹出机器的最小次数。从后往前遍历对于位置 i1. 直接向右跳dp[i] (i jump[i] n) ? 1 : dp[i jump[i]] 12. 利用左侧跳转优化右侧由于从任意右侧位置 j ( i) 都可以向左一步跳到 i所以如果 dp[j] dp[i] 1则更新 dp[j] dp[i] 1。当遇到 dp[j] dp[i] 1 时即可 break因为更左侧的位置已经被更优地更新过了。这个 break 剪枝使得均摊时间复杂度接近 O(N)。---Java 代码javaclass 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 516≥6 → 1 1 — 14 1 4156 → dp[5]12 2 dp[5]1 3, break 23 1 3146 → dp[4]13 3 dp[4]2 4, break 32 1 2136 → dp[3]14 4 dp[3]3 5, break 31 5 156≥6 → 1 1 dp[2]3≥2 → 2; dp[3]3≥2 → 2; dp[4]2≥2 → 2; dp[5]12 break 10 2 0226 → dp[2]13 3 dp[1]14, break 3输出3 ✓路径0 → 2 → 1 → 弹出