Dynamic Programming - Jump Game (DP Approach)

Given array where each element is the max jump length from that position, determine if you can reach the last index.

Input: nums=[2,3,1,1,4] → Output: true

Input: nums=[3,2,1,0,4] → Output: false

DP: dp[i] = true if index i is reachable. Propagate reachability forward.

dp[0] = true, rest false
For each i where dp[i]==true: mark dp[i+1..i+nums[i]] as true
Return dp[n-1]

public boolean canJump(int[] nums) { boolean[] dp = new boolean[nums.length]; dp[0] = true; for (int i = 0; i < nums.length; i++) { if (!dp[i]) continue; for (int j = 1; j <= nums[i] && i + j < nums.length; j++) dp[i + j] = true; } return dp[nums.length - 1]; }

Time Complexity: O(n^2)
Space Complexity: O(n)