Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array. Determine if you are able to reach the last index.

• Time: O(n)
• Space: O(n)

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

Jump Game II

For example: Given array A = [2,3,1,1,4] The minimum number of jumps to reach the last index is 2.

• Time: O(n)
• Space: O(n)

public int jump(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 1; dp[i] != Integer.MAX_VALUE && j <= nums[i] && i + j < n; j++) {
            dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
        }
    }
    return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
}