ДП вчимося бачити стани, вигадувати перехід
Щоб цей етап нерозуміння закінчився у вас швидше, я і написав попередню статтю. Ок, я казав, що треба вигадати перебір, а потім відсікти повторне обчислення однакових гілок перебору. Але буває так, що можна придумати 100500 варіантів перебору, і далеко не в кожному будуть кроки, що повторюються, запам'ятовування яких зробить рішення розумним за складністю стосовно даних в умові обмежень. Так це так, потім ви навчитеся бачити правильні підходи, але крім цієї побитої фрази, що «треба вирішувати завдання, щоб навчитися їх вирішувати» мені є що сказати.
Вся потрібна інформація є в умові, іноді на неї потрібно подивитися на звороті, змінити напрямок перебору в якусь іншу сторону. Давним-давно я зіткнувся з деякими складнощами при вирішенні задачі Folding і SkidanovAlex провів для мене її розбір ICQ. Як мені здається, приблизно з цього часу я почав вирішувати ДП краще та частіше. Давайте розберемо її. Умова коротко: є рядок із великих латинських літер, і правила за якими ми можемо його стискати, потрібно стиснути рядок так, щоб його стиснута версія була якомога коротшою. Стиснення описується як те, що є собою стислий рядок і у що він розтискається:
1) Стока, що складається тільки з літер, є стисла стока, і розтискається вона в саму себе. 2) Рядок, що є конкатенацією двох стислих рядків A і B , і розжимається він у конкатенацію рядків U(A) і U(B) , де U(X) – те, у що розтискається рядок X 3) Рядок D(X) де D ціле число більше 1, а X стислий рядок, розтискається в конкатенацію D рядків U(X) Приклади U(“A2(B)”) = “ABB” , U(“3(2) (A)2(B))”) = “AABBAABBAABB” .
Ок, давайте подумаємо, що ми можемо робити з рядками? Ми можемо або склеювати два різні рядки в один, або склеювати N однакових рядків X водну виду N(X). Або можна подивитися на завдання з іншого боку, і навпаки, розділяти рядок на два довільні підрядки, або на кілька однакових. Обидва варіанти мають право на існування, але використовуємо другий варіант, тому що його зручно реалізувати рекурсивно, і моєму мозку він якось більш зрозумілий. Тобто. намагаємося застосувати рекурсивний підхід. Ось дали нам рядок S який треба стиснути, ми можемо розбити її на дві, стиснути їх (рекурсивно) і склеїти результат, або розбити рядок на N однакових підрядків, стиснути цей підрядок Z і повернути рядок N(Z).
Як результат я зберігаю прямо рядок, але достатньо насправді зберігати тільки довжину і не забути про додаткову інформацію для відновлення відповіді у вигляді рядка. Рекурсію можна розгорнути у цикли, тобто. вважати те саме, перебираючи підрядки у порядку зростання довжини. Але це залишається читачеві як вправу.