Jump Game (DP Approach)

Share

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

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

Solution Approach

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]
Java
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)