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

Дан массив arr[] , состоящий из значений (0, 1, 2, 3) длины N, представляющих тип работы, которую можно выполнить в любой i-й день, так что задача относится либо к типу A, либо к типу B. Каждое значение в массиве определяется как:
0 – Нет доступных задач.
1 – доступна задача типа B.
2 – доступна задача типа А.
3 – Доступны как задача A, так и задача B.

Если один и тот же тип задачи не может быть выполнен в течение двух дней подряд, задача состоит в том, чтобы свести к минимуму количество дней, в течение которых не будет выполняться ни одна задача.

Примеры:

Input: N = 4, arr = {0, 1, 3, 2}
Output : 2
Explanation : Following are the types of tasks done in each day.
On the 1st day there is no tasks so he does nothing and count becomes 1. 
On the 2nd day, he performs task of type B. 
On the 3rd day there are both tasks but as he had done task of type B on the previous day so he performs task A. 
On the last day there is task A available but he had done the same task on the previous day so he does nothing and count becomes 2.
Therefore, 2 is the final answer. 

Input: N = 8, arr[] = {0, 1, 3, 2, 0, 2, 3, 3}
Output: 3

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

• Объявите переменную, скажем, count = 0, чтобы сохранить ответ.
• Если arr[i]=0, задачи нет, поэтому ничего не делайте и увеличьте количество.
• Если arr[i]=1, доступна только задача B, если задача последнего дня была B, то ничего не делайте и увеличьте количество, иначе выполните задачу B.
• Если arr[i]=2, доступна только задача A, если задача последнего дня была A, то ничего не делайте и увеличьте количество, иначе выполните задачу A.
• Если arr[i]=3, и задача последнего дня была A, тогда выполните задачу B, если задача последнего дня была B, тогда выполните задачу A, в противном случае выполните задачу, которая сведет к минимуму количество дней, в течение которых задача не выполняется.
• Используйте переменную last, чтобы отслеживать задачу предыдущего дня, которая может принимать следующие значения:
  • 0 – задание не выполняется.
  • 1 – задание типа А выполнено
  • 2 – задание типа Б выполнено

Ниже приведена реализация описанного выше подхода.

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

Эффективный подход: для оптимизации описанного выше подхода можно использовать динамическое программирование. Используйте запоминание для сохранения предыдущего состояния, чтобы эти предыдущие состояния можно было использовать для вычисления дальнейших результатов.

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

Временная сложность: O(N), где N — размер arr[].
Вспомогательное пространство: O(N), где N — размер arr[].