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).