Модуль: Паттерны в динамическом программировании

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

Если задача сводится к тому, что необходимо разбить массив на непересекающиеся подотрезки (последовательность подряд идущих элементов) оптимальным образом (или посчитать количество подходящих разбиений), то стоит попробовать решить ее с помощью динамического программирования.

Примерная схема решения такая:
dp[i] - ответ для первых i элементов

Подсчет dp[i]: так как мы рассматриваем только первые i элементов, то i-й будет последним и значит, что этот элемент будет в последнем подотрезке и при этом самым правым там. Поэтому мы можем перебрать левую границу последнего подотрезка j. В процессе перебора будем подсчитывать значение этого подотрезка и если он является корректным, то пересчитаем dp[i] через dp[j - 1] и значение подотрезка [j;i].

Рассмотрим следующую простую задачу: дан массив из целых чисел, необходимо разбить его на минимальное количество непересекающихся подотрезков, чтобы каждое число входило в какой-нибудь подотрезок и чтобы в каждом подотрезке были одинаковые числа. Например, для массива 1 2 2 3 3 3 2 1 1 оптимальное разбиение выглядит так: [1] [2 2] [3 3 3] [2] [1 1]. Эта задача несложно решается простым проходом по массиву (все одинаковые подряд идущие элементы помещаем в один подотрезок), но мы решим ее с помощью динамического программирования для примера.
 

	int n;
	cin >> n;

	// заполняем массив с 1-индексацией
	vector arr(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	// изначально ставим +оо в значения дп
	vector dp(n + 1, 1000000000);

	// массив длины ноль разбивать не нужно, поэтому для него ответ 0
	dp[0] = 0;

	// считаем ответ для dp[i] по возрастанию i
	for (int i = 1; i <= n; i++) {
		// в текущий момент arr[i] - последний элемент, значит он будет самым правым числом в последнем подотрезке
		// переберем все варианты того, где этот последний подотрезок начинался
		for (int j = i; j > 0; j--) {
			if (arr[j] != arr[i]) {
				// если встретили элемент, который не равен последнему, то подотрезок будет содержать разные числа, а это не подходит по условию
				// продолжать уже нет смысла, т.к. сдвигая левую границу левее, этот элемент не пропадет, поэтому делаем break
				break;
			}

			// представляем, что последний подотрезок был [j;i]
			// значит надо взять оптимальное разбиение первых j-1 элементов и прибавить 1 (сам подотрезок  [j;i])
			dp[i] = min(dp[i], dp[j - 1] + 1);
		}
	}
	cout << dp[n];