Долгое время задачи на ДП ставили меня в тупик. Во время соревнования не понимаешь, как это решать, кроме полного перебора.

Во время разбора говорят: «давайте заведем массив d[i][j], где i это количество ёжиков, а j количество белочек, а в самом массиве d[i][j] будем хранить чего-то там». Думаешь «ЩИТО? WTF, как бы я на контесте догадался, что мне надо завести двумерный массив, а не трехмерный, например? Почему индексы это ежики и белочки, а не стоимость белочек и оставшиеся у зайчика деньги?» потом говорят «понятно, что d[i][j] = d[i – 1][j] + 100500 * d[i – 1][j + 13] + 42» Смотришь, ну вроде да, логично, но как блин к этому прийти-то? Как бы я понял, что использовать в качестве индексов? В каком порядке эти индексы перебирать? Как понять КАК рассчитывать значение d[i][j] из таких-то предыдущих вычисленных значений?

Чтобы этот этап непонимания закончился у вас быстрее я и написал предыдущую статью. Ок, я говорил, что нужно придумать перебор, а потом отсечь повторное вычисление одинаковых веток перебора. Но ведь бывает так, что можно придумать 100500 вариантов перебора, и далеко не в каждом будут повторяющиеся шаги, запоминание которых сделает решение разумным по сложности применительно к данным в условии ограничениям. Да это так, потом вы научитесь видеть правильные подходы, но кроме этой избитой фразы что «надо решать задачи, чтобы научиться их решать» мне есть что сказать.

Вся нужная информация есть в условии, иногда на неё нужно посмотреть с обратной стороны, изменить направление перебора в какую-то другую сторону. Давным-давно я столкнулся с некоторыми сложностями при решении задачи Folding и AlexSkidanov провел для меня её разбор по 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).

string D(int L, int R) // результат сжатия для подстроки состоящей из символов i, L <= i < R
{
	if (L + 1 == R) // осталась одна буква, вернем её
		return string(s + L, s + R);
	if (d[L][R].size()) // мы уже считали результат для этой подстроки, вернём то что ранее насчитали
		return d[L][R];
	string res = string(s + L, s + R);// изначальный результат это сама подстрока
	int n = R - L;
	for (int i = 1; i <= n; i++) // пытаемя разбить на n / i одинаковых
		if (n / i >= 2 && n % i == 0 && ok(s + L, n, i)) //
		{
			string zip = Str(n / i) + "(" + D(L, L + i) + ")";
			if (res.size() > zip.size())
				res = zip;
		}
	for (int i = L + 1; i < R; i++) { // пытаемся разбить на две любые
		string zip = D(L, i) + D(i, R);
		if (res.size() > zip.size())
			res = zip;
	}
	d[L][R] = res;
	return res;
}

Int main() {
	cin >> s;
	cout << D(0, s.size()) << endl;
}

В качестве результата я храню прямо строку, но достаточно на самом деле хранить только длину, и не забыть про дополнительную информацию для восстановления ответа в виде строки. Рекурсию можно развернуть в циклы, т.е. считать то же самое, перебирая подстроки в порядке возрастания длины. Но это остается читателю в качестве упражнения.