Со вчерашнего дня накинулся на тему динамического программирования. По сути вся задача сводится к определению состояния, атомарных(базовых) величин и построению рекурентной формулы. Решая простые примеры, казалось, что все понятно. Однако столкнувшись с олимпиадными задачами, очень сложно выявить возможность декомпозировать задачу на подзадачи.

Вот, например, задача 1409F из архива codeforces. В строке нужно изменить определенное количество символов, для того, чтобы слово из 2-х букв было бы подпоследовательностью как можно большее количество раз. В качестве состояний не понятно, что взять. Думал, например, взять количество подпоследовательностей в строке длины n-1. Но это состояние не имеет смысла из-за того, что количество перестановок ограниченное число. Как решить эту задачу, я пока не имею представления.

Выводы следующие: разобрать методики формирования состояний для случаев, когда задачу можно решить при помощи методики дп; разобраться с двумерным динамическим программированием.