Most of the solutions I've seen looks for the maximum reachable index and then checks for `n-1`

.

What if we instead look for the answer more directly:

- Can we jump to
`last`

from any`i`

? - If so, can we jump to
`i`

from any`i'`

before that? - ... repeating until we're asking whether can we jump to
`0`

? - or failing to find any
`i`

to jump from.

Below is an `O(n^2)`

time implementation and it's also an `O(n)`

space deep recursion in the worst case (`[1,1,...,1,1,x]`

):

```
public boolean canJumpSlow(int[] nums) {
return canJumpSlow(nums, nums.length - 1);
}
boolean canJumpSlow(int[] nums, int last) {
if (last == 0) return true;
for (int i = 0; i < last; ++i) {
int needToJump = last - i, canJump = nums[i];
if (needToJump <= canJump) {
return canJumpSlow(nums, i);
}
}
return false;
}
```

By reversing the iteration we can do it in `O(n)`

time, but the `O(n)`

space recursion is still there:

```
public boolean canJumpFast(int[] nums) {
return canJumpFast(nums, nums.length - 1);
}
boolean canJumpFast(int[] nums, int last) {
if (last == 0) return true;
for (int i = last - 1; i >= 0; --i) {
int needToJump = last - i, canJump = nums[i];
if (needToJump <= canJump) {
return canJumpFast(nums, i);
}
}
return false;
}
```

Here's an `O(n)`

time, `O(1)`

space iterative version, which is a simple linear walk (backwards):

```
public boolean canJump(int[] nums) {
int last = nums.length - 1;
for (int i = last - 1; i >= 0; --i) {
int needToJump = last - i, canJump = nums[i];
if (needToJump <= canJump) {
last = i;
}
}
return last == 0;
}
```

I'm curious about insights into how this is equivalent to the DP solutions which look for

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