LeetCode_数组_中等_45.跳跃游戏II

这里写目录标题

• 1.题目
• 2.思路
• 3.代码实现（Java）

1.题目

给你一个非负整数数组 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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/jump-game-ii

2.思路

（1）动态规划

使用动态规划最重要的一点就是找出状态转移方程，这里定义一个长度为nums.length数组dp，且dp[i]=j表示从数组下标为0的位置跳到下标为 i 的位置需要的最少跳跃次数为 j，dp[0]=0。然后从数组nums中下标为1的元素开始遍历，并且计算dp[i]的值，当遍历结束后，dp[nums.length-1]的值即为题目所求，将其直接返回即可。

那么现在的关键在于如何求出dp[i]，可以这样考虑，对于当前元素nums[i]，先从下标为0的位置开始寻找第一个可以直接跳到当前下标为i的位置 j，并且根据前面的定义可知dp[j]已经是从数组下标为0的位置跳到下标为 j 的位置需要的最少跳跃次数，所以可以推出状态转移方程为dp[i]=dp[j]+1，然后根据这来编写代码即可。

3.代码实现（Java）

//（1）动态规划
public int jump(int[] nums) {
    int length=nums.length;
    //dp[i]=j:从数组下标为0的位置跳到下标为i的位置需要的最少跳跃次数为j
    int[] dp=new int[length];
    dp[0]=0;
    for(int i=1;i<length;i++){
    	//从下标为0的位置开始寻找第一个可以直接跳到当前下标为i的位置
        int j=0;
        //nums[j]<i-j:说明从下标为j的位置不能直接跳到当前下标为i的位置
        //j++:将跳跃位置向后移动一个长度
        while(j<i && nums[j]<i-j){
            j++;
        }
        //此时已找到第一个可以直接跳到当前下标为i的位置j，且dp[j]是从数组下标为0的位置跳到下标为j的位置需要的最少跳跃次数
        dp[i]=dp[j]+1;
    }
    return dp[length-1];
}