Минимизировать общую стоимость выбора K уникальных подпоследовательностей из заданной строки

Для заданной строки S длины N и положительного целого числа K задача состоит в том, чтобы найти минимальную общую стоимость выбора K уникальной подпоследовательности заданной строки S , при которой стоимость выбора подпоследовательности равна (длине S — длине этого подпоследовательность) . Если невозможно выбрать K уникальной подпоследовательности, то выведите « -1 ».

Примеры:

Input: S = “efef”, K = 4
Output: 3
Explanation: There are 4 subsequences – “efef”, “efe”, “eef” and “fef”. 
Hence, the total cost is 0 + 1 + 1 + 1 = 3.

Input: S = “aaaaa”, K = 40
Output: -1

Наивный подход: самый простой подход состоит в том, чтобы сгенерировать все возможные различные подпоследовательности заданной строки S и выбрать K уникальных подпоследовательностей максимально возможной длины. После выбора K подпоследовательностей результатом будет ( N*K — сумма длин всех выбранных K подпоследовательностей .)

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

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью динамического программирования. Идея состоит в том, чтобы инициализировать двумерный массив DP таким образом, чтобы dp[i[j] означало сумму длин уникальной подпоследовательности длины i , заканчивающейся символом j . Теперь после предвычисления выберите те K длин подпоследовательности, сумма длин которых максимальна. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную ans как 0.
• Инициализируйте 2D-массив dp[N+1][128] со значением 0.
• Перебрать диапазон [0, N), используя переменную i , и выполнить следующие задачи:
  • Повторите шаги [i+1, 1), используя переменную len , и выполните следующие задачи:
    • Установите dp[len][s[i]] как аккумулировать (dp[len – 1].begin(), dp[len – 1].end(), 0L).
  • Установите dp[1][s[i]] равным 1.
• Инициализируйте вектор v[N+1] со значениями 0.
• Установите v[0] как 1.
• Переберите диапазон [1, N], используя переменную i , и выполните следующие задачи:
  • Установите v[i] как аккумулировать (dp[i].begin(), dp[i].end(), 0L).
• Обратить вектор v[].
• Повторите цикл for, используя переменную i , и выполните следующие задачи:
  • Инициализировать переменную можно как минимум k или v[i].
  • Вычтите значение cantake из k .
  • Увеличьте значение ans на i*cantake.
• После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

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

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