Задача: Минимальное количество прыжков для достижения цели
Учитывая массив целых чисел, где каждый элемент представляет максимальное количество шагов, которые могут быть сделаны из этого элемента. Напишите функцию, чтобы вернуть минимальное количество переходов для достижения конца массива (начиная с первого элемента). Если элемент равен 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++;
// else if i is within range of arr[j],
// jumps for ith element would be jumps[j]+1
} else if (arr[j] + j >= i && j < i) {
jumps[i] = jumps[j] + 1;
i++;
} else {
printf("solution does not exist");
return -1;
}
}
printf("jumps: ");
for (i = 0; i < n; i++) {
printf("%d, ", jumps[i]);
}
return jumps[n - 1];
}
Пример:
1.) изначально i=1, j=0 и arr[] = {1, 3, 6, 1, 0, 9};
jumps[] = 0,0,0,0,0,0
2.), поскольку i находится в диапазоне от arr[j] т.е. i<= j+arr[j], количество прыжков, необходимых для перехода в i-ю позицию, будет минимальным числом прыжков до j-й позиции + 1.
i=2, j=0, jumps[] = 0,1,0,0,0,0
3.) i>j+arr[j] т.е. j++;
i=2, j=1, jumps[] = 0,1,0,0,0,0
4.) i<=j+arr[j] т.е. jumps[i] = jumps[j]+1;
i=3, j=1, jumps[] = 0,1,2,0,0,0
5.) i<=j+arr[j] т.е. jumps[i] = jumps[j]+1;
i=4, j=1, jumps[] = 0,1,2,2,0,0
6.) i<=j+arr[j] т.е. jumps[i] = jumps[j]+1;
i=5, j=1, jumps[] = 0,1,2,2,2,0
7.) i>j+arr[j] т.е. j++;
i=5, j=2, jumps[] = 0,1,2,2,2,0
8.) i<=j+arr[j] т.е. jumps[i] = jumps[j]+1;
i=6, j=2, jumps[] = 0,1,2,2,2,3
------ END ------
Я не могу понять, в какой тестовой ситуации эта программа не будет работать. Я спрашиваю об этом, потому что в Интернете оптимизированное решение использует DP, который является O (n ^ 2). Мое решение - это линейное время. то есть O (n). Поэтому я предполагаю, что есть некоторые случаи, которые этот алгоритм не будет обрабатывать. Поэтому мне любопытно, в каких случаях он не справляется.
Ваша помощь будет оценена.
Спасибо.
