Given an array of non-negative integers nums, you start at the first index. Each element represents the maximum jump length from that position. Return true if you can reach the last index, false otherwise.
Example 1
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step to index 1, then 3 steps to the last index.
Example 2
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You always land on index 3, whose max jump is 0 — index 4 is unreachable.
1 <= nums.length <= 10^40 <= nums[i] <= 10^5A DP formulation works: reachable[i] is true if some earlier reachable[j] can jump far enough to reach i — but this checks many (i, j) pairs, O(n^2).
You don't actually need to know EVERY reachable index individually — only the single FARTHEST index reachable so far.
If the current index ever exceeds the farthest-reachable mark accumulated from all earlier positions, it's provably unreachable — stop immediately.
public boolean canJumpDP(int[] nums) {
boolean[] reachable = new boolean[nums.length];
reachable[0] = true;
for (int i = 0; i < nums.length; i++) {
if (!reachable[i]) continue;
for (int step = 1; step <= nums[i] && i + step < nums.length; step++) {
reachable[i + step] = true;
}
}
return reachable[nums.length - 1];
}Time: O(n^2) worst case · Space: O(n)