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

Предыдущий
вопрос Следующий
вопрос

Для подсчета количества уникальных подпоследовательностей из последовательности чисел длиной 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] =
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 -
return sum(dp[1:]
arr = [8, 2, 4, 6
print(count_unique_subsequences(arr)) # Вывод: 15

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