本文共 1296 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要找到从数组的第一个位置到最后一个位置所需的最小跳跃次数。我们可以使用动态规划的方法来解决这个问题，从最后一个位置开始向前遍历，记录每个位置所需的最小跳跃次数。

方法思路

解决代码

public class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            int step = nums[i];
            if (i + step >= n - 1) {
                dp[i] = 1;
            } else {
                for (int s = step; s >= 0; s--) {
                    if (i + s < n && dp[i + s] + 1 < dp[i]) {
                        dp[i] = dp[i + s] + 1;
                    }
                }
            }
        }
        return dp[0];
    }
}

代码解释

• 初始化：创建一个 dp 数组，长度与输入数组相同，所有元素初始化为 Integer.MAX_VALUE，最后一个位置设为 0。
• 从后向前遍历：从倒数第二个位置开始，逐步向前遍历每个位置。
• 跳跃处理：对于每个位置，计算其最大跳跃长度。如果可以直接到达终点，跳跃次数设为 1。否则，逐步减少跳跃长度，找到最小的跳跃次数。
• 更新最小跳跃次数：在每一步中，更新当前位置的最小跳跃次数。

这种方法确保了我们能够以最少的跳跃次数到达数组的最后一个位置。

转载地址：http://uwzcz.baihongyu.com/