maximum-number-of-jumps-to-reach-the-last-index

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed array <code>nums</code> of <code>n</code> integers and an integer <code>target</code>.

You are initially positioned at index <code>0</code>. In one step, you can jump from index <code>i</code> to any index <code>j</code> such that:

<ul>
	<li><code>0 &lt;= i &lt; j &lt; n</code></li>
	<li><code>-target &lt;= nums[j] - nums[i] &lt;= target</code></li>
</ul>

Return the maximum number of jumps you can make to reach index <code>n - 1</code>.

If there is no way to reach index <code>n - 1</code>, return <code>-1</code>.

&nbsp;
Example 1:

<pre>
Input: nums = [1,3,6,4,1,2], target = 2
Output: 3
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1. 
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3. </pre>

Example 2:

<pre>
Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5. </pre>

Example 3:

<pre>
Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1. 
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length == n &lt;= 1000</code></li>
	<li><code>-109&nbsp;&lt;= nums[i]&nbsp;&lt;= 109</code></li>
	<li><code>0 &lt;= target &lt;= 2 * 109</code></li>
</ul>

maximumJumps

Maximum Number of Jumps to Reach the Last Index

Jump Game II

jump-game-ii

跳跃游戏 II

Frog Jump

frog-jump

青蛙过河

Jump Game III

jump-game-iii

跳跃游戏 III

Jump Game IV

jump-game-iv

跳跃游戏 IV

Minimum Jumps to Reach Home

minimum-jumps-to-reach-home

到家的最少跳跃次数

Jump Game VII

jump-game-vii

跳跃游戏 VII

Array

Dynamic Programming

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

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

<ul>
	<li><code>0 &lt;= i &lt; j &lt; n</code></li>
	<li><code>-target &lt;= nums[j] - nums[i] &lt;= target</code></li>
</ul>

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

如果无法到达下标 <code>n - 1</code> ，返回 <code>-1</code> 。

&nbsp;

示例 1：

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

示例 2：

<pre>输入：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 。 </pre>

示例 3：

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

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= nums.length == n &lt;= 1000</code></li>
	<li><code>-109&nbsp;&lt;= nums[i]&nbsp;&lt;= 109</code></li>
	<li><code>0 &lt;= target &lt;= 2 * 109</code></li>
</ul>