Given an array A of non-negative integers, you are initially positioned at index 0 of the array.A[i] means the maximum jump distance from that position (you can only jump towards the end of the array).Determine if you are able to reach the last index.

Assumptions

• The given array is not null and has length of at least 1.

Examples

• {1, 3, 2, 0, 3}, we are able to reach the end of array(jump to index 1 then reach the end of the array)
• {2, 1, 1, 0, 2}, we are not able to reach the end of array

Approach: Dynamic Programming

Base Case: m[n - 1] = true

Induction Rule: m[i] represents i-th number can be reached or not. if m[j] = true && input[i] >= j - i , j is from i + 1 to target.

public class Solution {
  public boolean canJump(int[] array) {
    // Write your solution here.
    if (array == null || array.length == 0) {
      return false;
    }
    boolean[] m = new boolean[array.length];
    m[array.length - 1] = true;
    for (int i = array.length - 2; i >= 0; i--) {
      for (int j = i + 1; j < array.length; j++) {
        if(m[j] && array[i] >= j - i) {
          m[i] = true;
          break;
        } 
      }
    }
    return m[0];
  }
}

倒着来的思路。

Time： O(n^2)

Space: O(n).