### The Problem

You are given an integer array `nums`. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return `true` if you can reach the last index, or `false` otherwise.

Check LeetCode link for more details and example input & output.

### Dynamic Programming Solutions

#### A Top Down Approach

A Java solution.

``````  public boolean canJump(int[] nums) {
return canJump(nums, 0, new Boolean[nums.length]);
}

/*
starting at position `index`, return `true` if it can reach the end.
*/
boolean canJump(int[] nums, int index, Boolean[] dp) {
// if we reach the end, i.e. the last index
if (index == nums.length - 1) {
dp[index] = true;
return true;
}
// check the cache
if (dp[index] != null) {
return dp[index];
}

// try all possible jumps from the position of the `index`
for (int i = 1; i <= nums[index]; i++) {
if (canJump(nums, index + i, dp)) {
dp[index] = true;
return true;
}
}
// tried all possible jumps and unable to reach the end,
// therefore, return false when getting here
dp[index] = false;
return false;
}
``````

#### A Bottom Up Approach

`dp[i]` means a sub problem. For this sub problem, it answers that if starting at the index `i`, whether it’s able to jump to the end.

`dp[i]` is `true`, if one of following conditions meets.

1. `i + nums[i]` is greater than or equal to `nums.length - 1`. That is from position `i`, we can jump to the end directly. Or,
2. Let’s say `dp[i, END]` is the sub problem jumping from `i` to the end. `dp[i, END]` is ture, when `dp[n1, n2]`, `dp[n2, n3]`, …, `dp[nn, END]` are true (n1 < n2 < n3 < … < nn < END) and `i + nums[i] >= n1`. That is, we can lower the target (lower from the original `END` to `n1`), by “chaining” the jump points to the end.

The condition 2 is more easier to meet.

Let’s iterate from the end to the index `0`. Our initial target is to reach the end, i.e. `nums.length - 1`. If `dp[i, END]` is ture, we lower the target, setting it to `i`.

``````  public boolean canJump(int[] nums) {
int target = nums.length - 1; // initial target
for (int i = nums.length - 1; i >= 0; i--) {
if (i + nums[i] >= target) {
target = i; // lower the target
}
}
// if index `0` can reach the target, target will be updated to `0`
if (target == 0) {
return true;
} else {
return false;
}
}
``````

The time complexity is `O(n)`.