We start from an array of integers, where each number means how many steps can be made from that position. First, we are on index 0 of the array, and we start jumping maximum the amount that we find at that index.
Input: int[] inputNumbers = {1, 4, 2, 7, 9, 3, 5, 8, 4, 7, 8}; Output: 3 Explanation: The jumps are: 1 -> 4 -> 9 -> 8. We start from index 0 where we have value 1. So, we jump one step and we arrive at value 4. This means our next options to choose from are: 2, 7, 9, 3. I chose 9 and reach the end of the array, to value 8. The same result is achieved by selecting 7. |
Solution:
1. private static int minimumJumps(int[] inputNumbers) { 2. int length = inputNumbers.length; 3. int[] jumps = new int[length]; 4. 5. if (length == 0 || inputNumbers[0] == 0) { 6. return -1; 7. } 8. 9. for (int i = 1; i < length; i++) { 10. jumps[i] = Integer.MAX_VALUE; 11. for (int j = 0; j < i; j++) { 12. if (i <= j + inputNumbers[j] && jumps[j] != Integer.MAX_VALUE) { 13. jumps[i] = Math.min(jumps[i], jumps[j] + 1); 14. break; 15. } 16. } 17. } 18. return jumps[length - 1]; 19. } 20.