题目描述
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.
Example1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example2:
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.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.
解题思路
- dp思想
- 首先要理解清楚题意，并不一定要最后剩余多少步精确到本跳数才能保证达到末尾
- 只要满足步数大于最后即可满足
- 维护一个一维数组 dp，其中 dp[i] 表示达到i位置时剩余的跳力，若到达某个位置时跳力为负了，说明无法到达该位置。
- 到达当前位置的剩余跳力跟什么有关呢，其实是跟上一个位置的剩余跳力（dp 值）和上一个位置新的跳力（nums 数组中的值）有关,这里新的跳力就是原数组中每个位置的数字，因为其代表了以当前位置为起点能到达的最远位置。
- 所以当前位置的剩余跳力（dp 值）和当前位置新的跳力中的较大那个数决定了当前能到的最远距离，而下一个位置的剩余跳力（dp值）就等于当前的这个较大值减去1，因为需要花一个跳力到达下一个位置
- dp状态转移方程 dp[i] = max(dp[i - 1], nums[i - 1]) - 1
- 中间如果出现了dp[i] < 0的情况，就不能满足题意
class Solution {
public:
bool canJump(vector<int>& nums) {
int dp[nums.size()] = {0};
dp[0] = nums[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 true;
}
};
