题目链接

LeetCode

题目描述

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • 1 <= nums.length <= 104

  • 0 <= nums[i] <= 1000

    解题思路

    方法一：动态规划

    dp[i] 代表跳到下标 i 处需要的最小跳跃数
    状态转移方程为：
    dp[j] = dp[j] == 0 ? dp[i] + 1 : Math.min(dp[j],dp[i] + 1);

    1. class Solution {
    2.   public int jump(int[] nums) {
    3.       int[] dp = new int[nums.length];
    4.       // dp[i] 代表跳到下标 i 处需要的最小跳跃数
    5.       // dp[0] = 0
    6.       for(int i = 0; i < nums.length; ++i){
    7.           for(int j = i + 1; j < nums.length && j <= i + nums[i]; ++j){
    8.               // 如果当前位置未被跳到过，则当前位置需要至少 dp[i] + 1 次，表示从 i 位置跳过来
    9.               // 如果当前位置被跳到过，则当前位置需要至少 Math.min(dp[j],dp[i] + 1) 次， 表示选择之前跳跃数和当前 i 处跳跃数之间的最小值
    10.               dp[j] = dp[j] == 0 ? dp[i] + 1 : Math.min(dp[j],dp[i] + 1);
    11.           }
    12.       }
    13.       return dp[nums.length-1];
    14.   }
    15. }

  • 时间复杂度 O(n)

  • 空间复杂度 O(n)

    方法二：贪心

    查找最远范围maxRight，
    上一次跳的最远位置为end
    res为步数

    class Solution {
  public int jump(int[] nums) {
      int len = nums.length;
      int maxRight = -1;
      int end = 0;
      int res = 0;
      for(int i = 0; i < len - 1; ++i){
          // 获取当前可以到达的最远位置
          maxRight = Math.max(maxRight, i + nums[i]);
          // end表示上一次跳跃的最远位置
          // 当上一次跳跃的位置为当前位置时，可以由当前位置跳到 maxRight
          if(end == i){
              end = maxRight;
              ++res;
          }
      }
      return res;
  }
}

  • 时间复杂度 O(n)

  • 空间复杂度 O(1)