DP #21. Minimum Jump To End. - mbhushan/dynpro GitHub Wiki

(21). Minimum Jump To Reach End.

Given an array, find minimum number to jumps to reach end of array, given you 
can jump at max as much as value at position in array.

Input:
A [] = {2, 3, 1, 1, 2, 4, 2, 0, 1, 1}

Formula:
// i goes from 0 to A.len-1;
// j goes from i+1 to A.len-1;
if (A[i] + i >= j) {
    jump[j] = max (jump[j], 1 + jump[i])
}

public int minJumps(int [] A) {
		
		int [] jumpNums = new int[A.length];
		int [] jumpIndex = new int[A.length];
		
		for (int i=0; i<A.length; i++) {
			jumpIndex[i] = i;
		}
		Arrays.fill(jumpNums, Integer.MAX_VALUE);

		jumpNums[0] = 0;
		
		for (int i=1; i<A.length; i++) {
			for (int j=0; j<i; j++) {
				if (A[j] + j >= i) {
					if (jumpNums[i] > 1 + jumpNums[j]) {
						jumpNums[i] =  1 + jumpNums[j];
						jumpIndex[i] = j;
					}
				}
			}
		}

Indexes	0	1	2	3	4	5	6	7	8	9
Jump Values	2	3	1	1	2	4	2	0	1	1
Max Jump (i=0)	0	1	1	inf	inf	inf	inf	inf	inf	inf
Actual Jump (i=0)	0	0	0	-1	-1	-1	-1	-1	-1	-1
Max Jump (i=1)	0	1	1	2	2	inf	inf	inf	inf	inf
Actual Jump (i=1)	0	0	0	1	1	-1	-1	-1	-1	-1
Max Jump (i=2)	0	1	1	2	2	inf	inf	inf	inf	inf
Actual Jump (i=2)	0	0	0	1	1	-1	-1	-1	-1	-1
Max Jump (i=3)	0	1	1	2	2	inf	inf	inf	inf	inf
Actual Jump (i=3)	0	0	0	1	1	-1	-1	-1	-1	-1
Max Jump (i=4)	0	1	1	2	2	3	3	inf	inf	inf
Actual Jump (i=4)	0	0	0	1	1	4	4	inf	inf	inf
Max Jump (i=5)	0	1	1	2	2	3	3	4	4	4
Actual Jump (i=5)	0	0	0	1	1	4	4	5	5	5
Max Jump (i=6)	0	1	1	2	2	3	3	4	4	4 (ans)
Actual Jump (i=6)	0	0	0	1	1	4	4	5	5	5

I7, I8 and I9 doesnt change the state, so those iterations are not mentioned above.

Minimum Jump To End

• Time Complexity: O(n^2)
• Space Complexity: O(n)