花花酱 LeetCode 403. Frog Jump

By zxi on April 5, 2025

肯定是用DP，但我自己想了一个奇怪的方法，勉强过了…

使用dp[i] = {steps}，表示可以达到stones[i]的最后一跳的unit的集合。
dp[0] = {0}
dp[1] = {1} if stones[1] = 1 else {}
然后对于stones[i]，枚举所有step – 1, step, step + 1三种情况，看看是否可以跳到新的石头上面（使用一个hashtable判断），如果可以的吧，把跳的unit存到dp[j]中。相当于推了。
需要使用hashset去重，不然会超时。

时间复杂度：O(n²)
空间复杂度：O(n²)

class Solution {

public:

bool canCross(vector<int>& stones) {

if (stones[1] != 1) return false;

unordered_map<int, int> m;

const int n = stones.size();

for (int i = 0; i < n; ++i)

m[stones[i]] = i;

// dp[i] = {steps} steps to jump to stone[i].

vector<unordered_set<int>> dp(n);

dp[0] = {0};

dp[1] = {1};

for (int i = 2; i < n; ++i) {

for (int last : dp[i - 1]) {

for (int cur = last - 1; cur <= last + 1; cur++) {

if (cur < 1) continue;

const int t = stones[i - 1] + cur;

auto it = m.find(t);

if (it != end(m)) dp[it->second].insert(cur);

}

return !dp.back().empty();

}

};

“优化”：由于每次只能k-1,k,k+1steps，所以最大的units和n是线性关系，达到stones[i]最多跳i+1个units。
可以用二维数组dp[j][k] := 是否可以通过k步跳到stones[j].
dp[j][k] = dp[i][k-1] || dp[i][k] || dp[i][k+1], k = stones[j] – stones[i]. 即从stones[i]跳到stones[j]，并且要求跳到stones[i]的可能步数中存在k-1,k,k+1。
时间复杂度和空间复杂度是一样的。

class Solution {

public:

bool canCross(vector<int>& stones) {

const int n = stones.size();

vector<vector<bool>> dp(n, vector<bool>(n + 1));

dp[0][0] = true;

for (int i = 1; i < n; ++i)

for (int j = 0; j < i; ++j) {

const int d = stones[i] - stones[j];

if (d >= n) continue; // undefined range.

dp[i][d] = dp[i][d] || (dp[j][d - 1] || dp[j][d] || dp[j][d + 1]);

}

return any_of(begin(dp.back()), end(dp.back()), [](bool x) { return x; });

}

};

花花酱 LeetCode 2770. Maximum Number of Jumps to Reach the Last Index

By zxi on July 11, 2023

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

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

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

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

If there is no way to reach index n - 1, return -1.

Example 1:

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.

Example 2:

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.

Example 3:

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.

Constraints:

2 <= nums.length == n <= 1000
-10⁹ <= nums[i] <= 10⁹
0 <= target <= 2 * 10⁹

Solution: DP

Let dp(i) denotes the maximum jumps from index i to index n-1.

For each index i, try jumping to all possible index j.

dp(i) = max(1 + dp(j)) if j > i and abs(nums[j] – nums[i) <= target else -1

Time complexity: O(n²)
Space complexity: O(n)

Python3

# Author: Huahua

class Solution:

def maximumJumps(self, nums: List[int], target: int) -> int:

n = len(nums)

@cache

def dp(i):

if i == n - 1: return 0

ans = -1

for j in range(i + 1, n):

if abs(nums[j] - nums[i]) <= target and dp(j) != -1:

ans = max(ans, 1 + dp(j))

return ans

return dp(0)

花花酱 LeetCode 45. Jump Game II

By zxi on April 28, 2019

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

Solution: Greedy

Jump as far as possible but lazily.

[2, 3, 1, 1, 4]
i    nums[i]   steps   near   far
-      -         0       0     0
0      2         0       0     2
1      3         1       2     4
2      1         1       2     4
3      1         2       4     4
4      4         2       4     8

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua, running time: 12 ms / 10.3 MB

class Solution {

public:

int jump(vector<int>& nums) {

int steps = 0;

int near = 0;

int far = 0;

for (int i = 0; i < nums.size(); ++i) {

if (i > near) {

++steps;

near = far;

}

far = max(far, i + nums[i]);

}

return steps;

}

};

花花酱 LeetCode 55. Jump Game

By zxi on November 15, 2018

Problem

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

Solution: Greedy

If you can jump to i, then you can jump to at least i + nums[i].

Always jump as far as you can.

Keep tracking the farthest index you can jump to.

Init far = nums[0].

far = max(far, i + nums[i])

check far >= n – 1

ex 1 [2,3,1,1,4]

i nums[i] i + nums[i] far

- - - 2

0 2 2 2

1 3 4 4

2 1 3 4

3 1 4 4

4 4 8 8

ex 2 [3,2,1,0,4]

i nums[i] i + nums[i] far

- - - 3

0 3 3 3

1 2 3 3

2 1 3 3

3 0 3 3 <- can not reach index 4, break

C++

// Author: Huahua, running time 16 ms

class Solution {

public:

bool canJump(vector<int>& nums) {

const int n = nums.size();

int far = nums[0];

for (int i = 0; i < n; i++) {

if (i > far) break;

far = max(far, i + nums[i]);

}

return far >= n-1;

}

};

Posts tagged as “jump”

花花酱 LeetCode 403. Frog Jump

花花酱 LeetCode 2770. Maximum Number of Jumps to Reach the Last Index

Solution: DP

Python3

花花酱 LeetCode 45. Jump Game II

Solution: Greedy

C++

花花酱 LeetCode 55. Jump Game

Problem

Solution: Greedy

C++