问题:达到结束的最小跳跃次数
给定一个整数数组,其中每个元素表示可以从该元素向前进行的最大步数.编写一个函数来返回到达数组末尾的最小跳转次数(从第一个元素开始).如果元素为0,那么我们就无法遍历该元素.
例:
输入:arr [] = {1,3,5,8,9,2,6,7,6,8,9}输出:3(1-> 3 - > 8 - > 9)第一个元素是1,所以只能转到3.第二个元素是3,所以最多可以制作3个步骤,即5个或8个或9个.
资料来源:http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/
我已经制作了一个线性时间算法来查找到达数组末尾所需的最小跳跃次数.
源代码如下:
int minJumpsUpdated(int arr[], int n)
{
int *jumps = malloc(n * sizeof(int)); // jumps[n-1] will hold the result
int i =1, j = 0;
jumps[0] = 0;
for (i = 1; i < n; ) {
// if i is out of range of arr[j], then increment j
if (arr[j] + j < i && j < i) {
j++; …