Возможно расположение клеток N в ряд безопасным способом. Запрет на наличие трех клеток с одним и тем же видом животных

Содержание: Подсчет безопасных вариантов расположения клеток

Объяснение: Для решения задачи нам нужно посчитать количество возможных безопасных вариантов расположения клеток. Здесь предполагается, что мы имеем N клеток, которые мы должны разместить в ряд. Безопасный способ означает, что в ряду не может быть трех клеток с одним и тем же видом животных подряд.

Чтобы решить эту задачу, мы можем использовать метод динамического программирования. Мы создадим массив dp, где dp[i] будет представлять количество безопасных вариантов расположения i клеток.

Инициализируем массив dp следующим образом: dp[0] = 1 (пустой ряд) и dp[1] = 3 (три возможных виды животных в одной клетке ряда).

Затем мы будем заполнять массив dp, используя следующее рекуррентное соотношение: dp[i] = 2 * dp[i-1] - dp[i-3].

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

Наконец, выводим значение dp[N], которое будет представлять количество безопасных вариантов расположения N клеток.

Демонстрация:
Ввод: N = 4
Вывод: 18
Объяснение: Есть 18 безопасных вариантов для расположения 4 клеток.

Совет: Для лучшего понимания концепции рекуррентного соотношения, вы можете посмотреть на таблицу значений dp для нескольких начальных значений N и заметить, как они связаны между собой. Программирование задачи может помочь вам лучше запомнить формулу и понять ее работу.

Практика: Сколько безопасных вариантов расположения клеток будет, если N = 6?