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

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

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

Примеры:

Input: N = 5, K = 3
Output: 2
Explanation: Two combinations of array A of size N, whose sum of product of adjacent pairs adds up to K=3.
A = [1, 1, 1, 1, 0]: Value =  (1*1) + (1*1) + (1*1) + (1*0) = 3
A = [0, 1, 1, 1, 1]: Value =  (0*1) + (1*1) + (1*1) + (1*1) = 3

Input: N = 5, K = 4
Output: 1
Explanation: 
A = [1, 1, 1, 1, 1]: Value =  (1*1) + (1*1) + (1*1) + (1*1) = 4

Input: N=2, K=3
Output: 0

Наивный подход: самый простой подход состоит в том, чтобы найти все возможные комбинации возможного массива и проверить каждую комбинацию по отдельности, чтобы определить, равна ли ее сумма K или нет.
Сложность времени:

Эффективный подход: Объясненный выше простой подход можно оптимизировать, запоминая результат каждого рекурсивного вызова в трехмерной матрице dp размера (K+1, N+1, 2), то есть dp[K+1][N+1][ 2]. Здесь каждый узел этой матрицы dp, скажем, dp[a][b] представляет количество возможных комбинаций размера b , имеющих сумму a, а последним элементом является c , где c может быть только 0 или 1. Теперь выполните следующие шаги, чтобы решить Эта проблема:

  1. Для начала создадим функцию combionsPossible с параметрами (N, idx, prev, val, K) , где N — размер формируемого массива, idx — индекс, до которого возможны все возможные комбинации массива (изначально 0) , prev — предыдущий элемент во вновь сформированном массиве (может быть только 0 или 1), val — сумма произведений до idx, а K — сумма произведений последовательных элементов. Эта функция вернет количество возможных комбинаций до индекса idx , имеющего сумму val и предыдущий элемент prev . Кроме того, запомните результат при возврате.
  2. Теперь из основной функции вызовите вышеуказанную функцию combionsPossible два раза со всеми одинаковыми начальными значениями, но только изменив prev на 0 в одном и 1 в другом , чтобы вычислить возможные комбинации всех массивов, начиная с 0 и 1.
  3. В каждом вызове проверьте базовые случаи, а именно:
    • Если val>K : вернуть 0, потому что после этого индекса есть 0 комбинаций, имеющих сумму K, поскольку сумма уже превышена.
    • Если idx=N-1 : это означает, что сформирован весь массив размера N. Поэтому просто верните 1, т.е. количество возможных комбинаций, если значение равно K. В противном случае верните 0.
  4. Кроме того, в каждом рекурсивном вызове проверяйте, запомнен ли уже его результат или нет. Если это так, просто верните это из массива dp .
  5. Теперь, если предыдущий элемент равен 1, сделайте два рекурсивных вызова:
    • Рассмотреть возможные комбинации с 1 в качестве текущего элемента. Итак, увеличьте val на 1 в этом вызове, потому что произведение текущего и предыдущего элемента (1*1=1) добавит 1 к текущей сумме.
    • Рассмотреть возможные комбинации с 0 в качестве текущего элемента. В этом случае val останется прежним.
  6. Если предыдущий элемент равен 0, то также сделайте два рекурсивных вызова: один для рассмотрения комбинаций с 1 в качестве текущего элемента, а другой для рассмотрения комбинаций с 0 в качестве текущего элемента. В обоих случаях val останется прежним.
  7. Сложите все значения, возвращенные вышеуказанными четырьмя вызовами функций, и верните это добавленное значение из текущей функции после запоминания.
  8. Выведите ответ в соответствии с приведенным выше наблюдением.

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


Временная сложность: O(N*K)

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