Количество двоичных строк, содержащих не более X последовательных единиц и Y последовательных нулей

Опубликовано: 20 Сентября, 2022

Даны два целых числа N и M (1 ≤ N, M ≤ 100), обозначающие общее количество единиц и нулей соответственно. Задача состоит в том, чтобы подсчитать количество возможных расстановок этих нулей и единиц так, что любая расстановка имеет не более X последовательных единиц и Y последовательных нулей (1 ≤ X, Y ≤ 10) . Поскольку количество аранжировок может быть очень большим, вычислите ответ по модулю 10 9 +7 .

Примеры:

 Input: N = 2, M = 3, X = 1, Y = 2
Output: 5
Explanation: All arrangements: 11000, 10100, 10010, 10001, 01100, 01010, 01001, 00110, 00101, 00011.
Out of these arrangements the valid arrangements are: 10100, 10010, 01010, 01001, 00101
So the number of arrangements possible are 5.

Input: N = 2, M = 2, X = 1, Y = 1
Output: 2

Интуиция:

  • Основная интуиция проблемы состоит в том, чтобы проверить все возможные варианты с помощью рекурсии.
  • Это приводит к чрезвычайно высокой временной сложности.
  • Поэтому нужна какая-то техника оптимизации.
  • Выбор табуляции. Это резко снижает общую сложность проблемы.
  • Использование итеративного подхода вместо традиционной рекурсии + запоминания делает его еще проще.

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

  • Используйте трехмерную сетку для хранения следующего {количество единиц, количество нулей, представляет последнее использованное значение (0, если A, 1, если B) }
  • Используйте вложенный цикл для 1 и 0.
  • На каждой итерации во вложенном цикле (i обозначает 1, j обозначает 0)
    • Если к текущей последовательности добавляются 1, добавьте количество последовательностей, образованных с i – k, (1 ≤ k ≤ X) 1 с и заканчивающихся нулями.
    • Если к текущей последовательности добавляются 0, добавьте количество последовательностей, образованных j – k, (1 ≤ k ≤ Y) 0 и заканчивающихся единицами.
  • Это дает ответ на каждую итерацию последовательности с i 1s и j 0s.

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


Временная сложность: O(N * M * (X+Y)).
Вспомогательное пространство: O(N * M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ