1.5 Jump Game II

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 index i (you can only jump towards the end of the array). Determine the minimum number of jumps you need to reach the end of the array. If you can not reach the end of the array, return -1.

Assumption: The given array is not null and length >= 1

Input: int[] array, length n

Output: int the min number of jumps needed to reach the end of the array

Solution:

1. Base case: dp[n - 1] = 0

2. Induction rule: dp[i] represents the min of jumps from index i to n - 1, there exists 0<=j<i where dp[j] is the min jumps to reach i

dp[i] = min(dp[i+1], dp[i+2],...dp[i + input[i]) + 1

e.g.
index	0	1	2	3	4
input	2	3	1	1	4
dp[i]	2	1	2	1	0	← filled from right to left

i = 0	case 1: dp[1] + 1 = 2
	    case 2: dp[2] + 1 = 3		min = 2

i = 1	case 1: dp[2] + 1 = 3
	    case 2: dp[3] + 1 = 2
	    case 3: dp[4] + 1 = 1		min = 1

TC: worst case [1,1,1,1,1] = O(n^2)

SC: int[] dp = O(n)

public int minJump(int[] array) {
  int n = array.length;
  int[] dp = new int[n];
  dp[0] = 0;
  for (int i = 1; i < n; i++) {
    dp[i] = -1; 			//initialize as can't reach to last index
    for (int j = 0; j < i; j++) {
      if ( i <= j + array[j] && dp[j] != -1) {
          if (dp[i] == -1 || dp[i] > dp[j] + 1) {
            dp[i] = dp[j] + 1;
          }
      }
    }
  }
  return dp[n - 1];
}