# My 5 lines DP solution in O(n) time with constant space, 19ms.

• This a DP solution, and the idea is to save the maximum jump length every time, if the maximum length be zero, than return false.

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

• Brilliant solution! I did a recursive function and even after all the optimizations, could not clear the benchmark test. This is simple and elegant.

• Same idea, but doesn't change the original array.

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

return true;
}
}``````

• Cleverer， there is no need to change the original array.

• this is exactly what i came up with too.. but I also put a check on updated A[i] (variable d in my case) if greater than n-1-i , then done..no need to process it further. Here is my code

``````class Solution {
public:
bool canJump(int A[], int n) {
int i=0;
if(n==1)
return true;
if(A[0] == 0)
return false;
//start observing from pos 1 (0 is handled in base case)
i = 1;
int d = A[0]; //d is max jump at previous position
while(i < n) {
d = max(d-1,A[i]); //everytime decrease jump by 1 and check for max
if(d >= (n-1-i)) //if you can jump till end - done!
return true;
if(d == 0) //if you can't jump anymore - done!
return false;
i++;
}
}
};``````

• Solid consideration!

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.