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

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

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

1) Канализацията, състояща се само от букви, е компресирана канализация и тя се разширява в себе си.

---