# [LeetCode] 55. Jump Game 跳跃游戏

2021年09月15日 阅读数：2

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

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

Determine if you are able to reach the last index.python

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:post

```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.```

Java:blog

```class Solution {
public boolean canJump(int[] A) {
int max = 0;
for(int i=0;i<A.length;i++){
if(i>max) {return false;}
max = Math.max(A[i]+i,max);
}
return true;
}
}　　```

Python:游戏

```class Solution:
# @param A, a list of integers
# @return a boolean
def canJump(self, A):
reachable = 0
for i, length in enumerate(A):
if i > reachable:
break
reachable = max(reachable, i + length)
return reachable >= len(A) - 1
```

C++: Backtrackelement

```class Solution {
public:
bool canJump(int A[], int n) {
int last=n-1,i,j;
for(i=n-2;i>=0;i--){
if(i+A[i]>=last)last=i;
}
return last<=0;
}
};
```

C++: DP

```class Solution {
public:
bool canJump(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
for (int i = 1; i < nums.size(); ++i) {
dp[i] = max(dp[i - 1], nums[i - 1]) - 1;
if (dp[i] < 0) return false;
}
return dp.back() >= 0;
}
};
```

C++: Greedy

```class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size(), reach = 0;
for (int i = 0; i < n; ++i) {
if (i > reach || reach >= n - 1) break;
reach = max(reach, i + nums[i]);
}
return reach >= n - 1;
}
};
```

[LeetCode] 45. Jump Game II 跳跃游戏 II