10— 达到末尾下标所需的最大跳跃次数【LeetCode2770】

题目

2770. 达到末尾下标所需的最大跳跃次数 - 力扣（LeetCode）

给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。

你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：

• 0 <= i < j < n
• -target <= nums[j] - nums[i] <= target

返回到达下标 n - 1 处所需的 最大跳跃次数 。

如果无法到达下标 n - 1 ，返回 -1 。

示例一：

输入：nums = [1,3,6,4,1,2], target = 2
输出：3
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 5 。 
可以证明，从 0 到 n - 1 的所有方案中，不存在比 3 步更长的跳跃序列。因此，答案是 3 。 

示例二：

输入：nums = [1,3,6,4,1,2], target = 3
输出：5
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 2 。 
- 从下标 2 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 4 。 
- 从下标 4 跳跃到下标 5 。 
可以证明，从 0 到 n - 1 的所有方案中，不存在比 5 步更长的跳跃序列。因此，答案是 5 。 

示例三：

输入：nums = [1,3,6,4,1,2], target = 0
输出：-1
解释：可以证明不存在从 0 到 n - 1 的跳跃序列。因此，答案是 -1 。 

提示：

• 2 <= nums.length == n <= 1000
• -109 <= nums[i] <= 109
• 0 <= target <= 2 * 109

解题

解法一

思路

本题同样是用到动态规划，使用动态规划可以很简单地解决问题。

首先建立一个存储每个索引处最多的到达方法dp[]，dp[i]表示到达nums[i]的最多的步数。然后用两个for循环，第一个for循环用来走nums数组，将nums数组每个索引走到的最大次数都存进dp[i]当中，第二个for循环用来看前面的索引处能不能到达第一个for循环到达的i，要是能到达，取最长的步数存入dp[i]中。

存储最大步数：dp[i] = Math.max(dp[i],dp[j]+1);

解决

class Solution {
    public int maximumJumps(int[] nums, int target) {
        int length = nums.length;
        //声明dp数组，用于动态规划，dp[i]记录的是到达nums[i]的长度
        int dp[] = new int[length];
        //默认索引0处的方法数为1
        dp[0] = 1;
        for(int i=1;i<length;i++){
            for(int j=0;j<i;j++){
                if(  (nums[i]-nums[j])<=target && (nums[i]-nums[j])>=-target && dp[j]!=0){
                    //可达且j也是可达，然后挑选最大的路进行记录
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        return dp[length-1]-1;
    }
}

结果

> 2023/07/17 18:33:35    
解答成功:
    执行耗时:15 ms,击败了95.33% 的Java用户
    内存消耗:42.5 MB,击败了78.94% 的Java用户