Привет, исследователь кода! 🖖 Сегодня мы с вами окунёмся в глубины наших воспоминаний. В жизни каждого из нас есть моменты, которые мы хотели бы вспомнить. Иногда мы помним фрагменты истории, но не уверены, действительно ли они являются частью нашего прошлого. Это как пытаться понять, является ли одна строка подпоследовательностью другой. Именно это мы и будем делать сегодня! Задача дня: у нас есть две строки, s и t. Нам нужно определить, является ли строка s подпоследовательностью t. Подпоследовательность...

Сегодня решим сложную задачу на динамическое программирование про поиск уникальных подпоследовательностей. Читаем условие: Сложность задачи складывается из нескольких пунктов: Напомню, что подстрока - это непрерывная последовательность символов с i-го до j-го. Или, на языке Python - это слайс s[i:j]. А подпоследовательность - это любая последовательность, которая может быть получена из исходной вычёркиванием произвольного числа символов. Количество подстрок O(N^2), а количество подпоследовательностей O(2^N), поэтому перебрать все не получится...