问题叙述性说明：

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.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

基本思路：

从每一个可达的节点产生新的可达节点。

依次类推。但用一个变量head记录当前可达最远的位置。对于i+A[i] < head 能够剪枝。

请见代码。

代码：

bool canJump(int A[], int n) { //C++vector<int> record(n,0);record[0] = 1;if(n == 1)return true;int head = 0;for(int i =0; i < n; i++){if(record[i] == 1 && i+A[i] > head){for(int j = head-i+1; j <= A[i]; j++){if(i+j == n-1)return true;record[i+j] = 1;}head = i+A[i];}}return false;}

版权声明：本文博客原创文章，博客，未经同意，不得转载。

总结

以上是生活随笔为你收集整理的[leetcode]Jump Game的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。