Сколько существует различных уникальных подпоследовательностей из последовательности цифр длиной N? Есть последовательность чисел, например 8 2 4 6.
У этого числа существует 41 подпоследовательность, это:
8246
246, 846, 826, 824
46, 26, 24, 46, 86, 84, 26, 86, 82, 24, 84, 82
4, 6, 2, 6, 2, 4, 4, 6, 8, 6, 8, 4, 2, 6, 8, 6, 8, 2, 2, 4, 8, 4, 8, 2
При этом 15 уникальных:
8246
246, 846, 826, 824
46, 26, 24, 86, 84, 82
4, 6, 2, 8
Какой алгоритм нужно использовать, что бы посчитать кол-во уникальных подпоследовательстей?
(Грубая сила не подходит. Нужно что-то более алгебраическое.)

21 Авг 2019 в 06:14
246 +1
0
Ответы
1

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

Пусть dp[i] - количество уникальных подпоследовательностей, которые можно составить из первых i элементов последовательности.

Тогда формула для вычисления dp[i] будет следующей:
dp[i] = 2 * dp[i-1] - dp[last[arr[i]] - 1], где last[arr[i]] - индекс последнего вхождения числа arr[i] до i-1 элемента.

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

Пример кода на Python:

def count_unique_subsequences(arr):
N = len(arr)
dp = [0] * (N + 1)
last = {}
dp[0] = 1
for i in range(1, N + 1):
dp[i] = 2 * dp[i-1]
if arr[i-1] in last:
dp[i] -= dp[last[arr[i-1]] - 1]
last[arr[i-1]] = i - 1
return sum(dp[1:])
arr = [8, 2, 4, 6]
print(count_unique_subsequences(arr)) # Вывод: 15

Этот алгоритм позволяет эффективно подсчитать количество уникальных подпоследовательностей из последовательности чисел длиной N.

20 Апр 2024 в 13:21
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир