Количество двоичных строк длиной не более N с установленным количеством бит, кратным K

Даны два целых числа N и K , задача состоит в том , чтобы найти количество двоичных строк не более N длины , которые можно составить так , чтобы количество последовательных единиц всегда было кратно K .

Пример:

Input: N = 3, K = 2
Output: 6
Explanation: Binary strings of atmost N length containing consecutive 1’s as a multiple of K are as follows:

1. Length 1: “0”, contains 0 consecutive 1.
2. Length 2: “00”, “11”, contains 0 and 2 consecutive 1’s respectively.
3. Length 3: “000”, “011”, “110”, contains 0 and two different combinations of 2 consecutive 1’s respectively.

So, total number of strings that can be formed is 6.

Input: N = 5, K = 4 
Output: 8

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

• Создайте рекурсивную функцию cntStrings(N, K) , которая возвращает количество строк длины N , имеющих последовательные единицы, кратные K . Это можно сделать, присвоив 1 следующим K последовательным индексам из текущего индекса и рекурсивно вызвав оставшуюся строку, или присвоив 0 текущему индексу и рекурсивно вызвав оставшуюся строку.
• Создайте массив dp[] , в котором хранятся запомненные значения вышеуказанной рекурсивной функции.
• Вызовите функцию cntStrings(i, K) для всех возможных значений i в диапазоне [1, N] и сохраните их сумму в переменной cnt .
• Значение, хранящееся в cnt , является требуемым ответом.

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

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