Минимизируйте количество удаляемых элементов массива, чтобы не менее K элементов были равны их значениям индекса.

Для заданного массива arr[] (индексация на основе 1), состоящего из N целых чисел и положительного целого числа K , задача состоит в том, чтобы найти минимальное количество элементов массива, которые необходимо удалить так, чтобы по крайней мере K элементов массива были равны их значениям индексов. . Если это невозможно сделать, то выведите -1 .

Примеры:

Input: arr[] = {5, 1, 3, 2, 3}  K = 2
Output: 2 
Explanation:
Following are the removal operations required:

• Removing arr[1] modifies array to {1, 3, 2, 3} -> 1 element is equal to its index value.
• Removing arr[3] modifies array to {1, 2, 3} -> 3 elements are equal to their index value.

After the above operations 3(>= K) elements are equal to their index values and the minimum removals required is 2.

Input: arr[] = {2, 3, 4}  K = 1
Output: -1 

Подход: Вышеупомянутая проблема может быть решена с помощью динамического программирования. Выполните следующие шаги, чтобы решить данную проблему.

• Инициализируйте двумерную таблицу dp таким образом, чтобы dp[i][j] обозначал максимальное количество элементов, значения которых равны их индексам, когда присутствует общее количество элементов j.
• Все значения в таблице dp изначально заполнены нулями .
• Итерация для каждого i в диапазоне [0, N-1 ] и j в диапазоне [0, i] есть два варианта.
  • Удалите текущий элемент, таблицу dp можно обновить как dp[i+1][j] = max(dp[i+1][j], dp[i][j]) .
  • Сохраните текущий элемент, тогда таблица dp может быть обновлена следующим образом: dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + (arr[ я+1] == j+1)) .
• Теперь для каждого j в диапазоне [N, 0] проверьте, является ли значение dp[N][j] больше или равным K . Возьмите минимум, если он найден, и верните ответ.
• В противном случае верните -1 в конце. Это означает, что возможный ответ не найден.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(N ² )