Продолжаем рассказывать про стандартные алгоритмические задачки для программистов — особенно о тех, которые часто просят реализовать на собеседованиях. Все такие задачи собраны в «Испытаниях» у нас на сайте. Сегодня будет задача «Сбалансированы ли скобки?» — ее описание и условие можно посмотреть на картинке...

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