Сделайте все элементы массива равными, многократно заменяя последовательные вхождения числа

Учитывая массив arr[] размера N , задача состоит в том, чтобы найти минимальное количество операций, необходимых для того, чтобы сделать все элементы массива равными , с помощью следующей операции:

1. Выберите любое число от 1 до N .
2. Выберите элемент из массива,
3. Замените все последовательные равные элементы выбранным числом.

Пример:

Input: arr[] = {1, 2, 5, 2, 1}, N = 5
Output: 2
Explanation: Following are the operations required to make all the elements in arr[] equal.
{1, 2, 2, 2, 1}, pick 2 and replace it with all consecutive 5s.
{1, 1, 1, 1, 1}, pick 1 and replace it with all consecutive 2s.
Therefore, Number of operations required = 2, which is minimum possible. 

Input: arr[] = {4, 4, 7, 4, 7, 7, 3, 3}, N = 7
Output: 3

Подход: Эту проблему можно решить с помощью динамического программирования . Идея состоит в том, чтобы продумать порядок исчезновения элементов внутри подинтервала до предела. В подынтервале [l, r] есть первый момент, когда элемент в позиции r будет равен нулю. И в этот момент времени будет подинтервал [i, r] исчезнувших элементов. Эти [i, r] были удалены за наименьшее количество шагов. В противном случае мы можем уменьшить количество шагов. Кроме того, на предыдущем шаге элемент в позиции r уже существовал. Итак, возможны два случая:

• Сегмент [i, r-1] уже удален ⇢ означает, что один элемент удален в позиции r , но это означает, что мы можем сначала удалить сегмент [l, r-1] , а затем удалить один элемент в позиции r .
• Сегмент [i+1, r-1] уже удален ⇢ означает, что удаляются сразу два элемента: на позициях r и i. Это должны быть одинаковые элементы.

Удалите все последовательные дубликаты в исходном массиве.
Используя приведенную выше идею, создайте двумерный массив dp, где dp[l][r] равно количеству шагов, необходимых для удаления всех элементов в диапазоне [l, r] . Тогда ответ будет (dp[0][n-1] – 1) (в индексации, основанной на 0), что есть не что иное, как удаление всего массива минус один шаг.

• Базовым случаем для нашего dp[][] является dp[i][i] = 1 . (Для удаления массива размера 1 требуется один шаг)
• для l < r , dp[l][r] будет первоначально установлено в dp[l][r-1] + 1 .
• для каждого элемента в позиции i с тем же значением, что и элемент в позиции r , обновить dp[l][r], если dp[l][i-1] + dp[i, r] меньше текущего значения dp[l] [р].

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

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