Recursive solution:
function canJumpFromPosition(position, nums) {
if (position === nums.length - 1) {
return true;
}
let furthestJump = Math.min(position + nums[position], nums.length - 1);
for (let nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
if (canJumpFromPosition(nextPosition, nums)) {
return true;
}
}
return false;
}
function canJump(nums) {
return canJumpFromPosition(0, nums);
}
Memoization:
function canJump(nums) {
// Initialize the memoization table with undefined values
let memo = new Array(nums.length).fill(undefined);
memo[memo.length - 1] = true; // The last index is always reachable from itself
function canJumpFromPosition(position) {
if (memo[position] !== undefined) {
// If we have already computed the value, return it
return memo[position];
}
// Compute the furthest jump from the current position
let furthestJump = Math.min(position + nums[position], nums.length - 1);
// Check if any position reachable from here can reach the end
for (let nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
if (canJumpFromPosition(nextPosition)) {
memo[position] = true;
return true;
}
}
memo[position] = false;
return false;
}
// Start the recursive check from the first index
return canJumpFromPosition(0);
}
Tabulation:
function canJump(nums) {
const n = nums.length;
// Create a DP table, initialized to false except the first element
const dp = new Array(n).fill(false);
dp[0] = true; // Start is always reachable from itself
// Fill the DP table from left to right
for (let i = 0; i < n; i++) {
if (dp[i]) { // If current index is reachable
// Calculate the furthest we can reach from here
let furthest = Math.min(i + nums[i], n - 1);
// Mark all reachable positions as true
for (let j = i + 1; j <= furthest; j++) {
dp[j] = true;
}
}
}
// If the last position is true, then it's reachable
return dp[n - 1];
}