Isenção de responsabilidade: o método descrito abaixo não é universal, mas muitas vezes pode resolver um problema ou ajudá-lo a encontrar a solução certa.
Se o problema se resume ao fato de que é necessário dividir a matriz em subsegmentos sem interseção (uma sequência de elementos consecutivos) de maneira ideal (ou contar o número de divisões adequadas), vale a pena tentar resolvê-lo usando programação dinâmica.
Um exemplo de esquema de solução é o seguinte:
dp[i] - resposta para os primeiros i elementos
Contando dp[i]: como estamos considerando apenas os primeiros i elementos, o i-ésimo elemento será o último, o que significa que este elemento estará no último subsegmento e, ao mesmo tempo, o mais à direita ali. Portanto, podemos iterar sobre o limite esquerdo do último subsegmento j. No processo de enumeração, calcularemos o valor deste subsegmento e, se estiver correto, recalcularemos dp[i] até dp[j - 1] e o valor do subsegmento [j;i].
Considere o seguinte problema simples: dado um array de números inteiros, você precisa dividi-lo em um número mínimo de subsegmentos sem interseção de modo que cada número seja incluído em algum subsegmento e cada subsegmento contenha os mesmos números. Por exemplo, para um array 1 2 2 3 3 3 2 1 1, a partição ideal se parece com isto: [1] [2 2] [3 3 3] [2] [1 1]. Essa tarefa é facilmente resolvida simplesmente passando pelo array (colocamos todos os mesmos elementos consecutivos em um subsegmento), mas vamos resolvê-la usando a programação dinâmica como exemplo.
int;
cin>> n;
// preenche array com 1-index
vetor arr(n + 1);
for (int i = 1; i <= n; i++)
cin>> arr[i];
// inicialmente define +oo para valores dp
vetor dp(n + 1, 1000000000);
// um array de comprimento zero não precisa ser dividido, então a resposta para ele é 0
dp[0] = 0;
// conta a resposta para dp[i] em i crescente
for (int i = 1; i <= n; i++) {
// atualmente arr[i] é o último elemento, então será o número mais à direita no último subsegmento
// percorre todas as opções de onde este último subsegmento começou
for (int j = i; j > 0; j--) {
if (arr[j] != arr[i]) {
// se você encontrar um elemento que não é igual ao último, o subsegmento conterá números diferentes e isso não se encaixa na condição
// não adianta continuar, porque deslocando a borda esquerda para a esquerda, este elemento não desaparecerá, então quebramos
quebrar;
}
// imagine que o último subsegmento foi [j;i]
// então você precisa pegar a partição ideal dos primeiros elementos j-1 e adicionar 1 (o próprio subsegmento [j; i])
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
Se os elementos não pertencerem a nenhum dos subsegmentos, basta considerar a opção apropriada, pois dp[i] = dp[i - 1]