You're given a non-empty array of positive integers where each integer represents the maximum number of steps you can take forward in the array. For example, if the element at index 1 is 3, you can go from index 1 to index 2, 3, or 4.
Write a function that returns the minimum number of jumps needed to reach the final index.
Note that jumping from index i to index i + x always constitutes one jump, no matter how large x is.
Sample Input
array = [3, 4, 2, 1, 2, 3, 7, 1, 1, 1, 3]
Sample Output
4 // 3 --> (4 or 2) --> (2 or 3) --> 7 --> 3
For each item i, check all previous items, calcuate the min jumps needed to that item.
// T: O(N ^ 2)
function minNumberOfJumps(array) {
const jumps = array.map(_ => Infinity)
jumps[0] = 0;
for (let i = 1; i < array.length; i++) {
for (let j = 0; j < i; j++) {
if (array[j] + j >= i) {
jumps[i] = Math.min(jumps[i], jumps[j] + 1)
}
}
}
return jumps[jumps.length - 1]
}
// Do not edit the line below.
exports.minNumberOfJumps = minNumberOfJumps;
标签:index,Min,--,jumps,Number,array,Jumps,DP,minNumberOfJumps From: https://www.cnblogs.com/Answer1215/p/16773507.html