DP се научава да вижда състояния, измисля преход

За да завърши този етап на неразбиране с вас по-бързо, написах предишната статия. Добре, казах, че трябва да измислите изброяване и след това да отрежете повторното изчисление на същите клонове за търсене. Но се случва да можете да измислите 100 500 опции за груба сила и не всеки ще има повтарящи се стъпки, запомнянето на които ще направи решението разумно от гледна точка на сложността, приложимо към ограничените данни. Да, това е така, тогава ще се научите да виждате правилните подходи, но освен тази коварна фраза, че „трябва да решите проблеми, за да се научите как да ги решавате“, имам какво да кажа.

Цялата необходима информация е в състоянието, понякога трябва да я погледнете от другата страна, да промените посоката на търсене в друга посока. Отдавна се сблъсках с някои трудности при решаването на проблема сгъване и SkidanovAlex го анализира за мен от ICQ. Струва ми се, че от около това време започнах да решавам DP по-добре и по-често. Да го разглобим.
Условие накратко: има низ от главни латински букви и правилата, по които можем да го компресираме, трябва да компресираме низа, така че компресираната му версия да е възможно най-кратка. Компресията се описва като компресиран низ и в какво се разширява:

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).

В резултат директно съхранявам низ, но е достатъчно да съхранявам само дължината и не забравяйте за допълнителна информация, за да възстановите отговора като низ. Рекурсията може да се разшири в цикли, т.е. помислете за едно и също нещо, итерирайки над поднизовете във възходящ ред на дължината. Но това е оставено на читателя като упражнение.