Descargo de responsabilidad: el método que se describe a continuación no es universal, pero a menudo puede resolver un problema o ayudarlo a encontrar la solución correcta.
Si el problema se reduce al hecho de que es necesario dividir la matriz en subsegmentos que no se intersecan (una secuencia de elementos consecutivos) de manera óptima (o contar el número de divisiones adecuadas), entonces vale la pena intentar resolverlo. usando programación dinámica.
Un esquema de solución de ejemplo es el siguiente:
dp[i] - respuesta para los primeros elementos i
Contando dp[i]: como solo estamos considerando los primeros i elementos, el i-ésimo elemento será el último, lo que significa que este elemento estará en el último subsegmento y, al mismo tiempo, el más a la derecha allí. Por lo tanto, podemos iterar sobre el límite izquierdo del último subsegmento j. En el proceso de enumeración, calcularemos el valor de este subsegmento y, si es correcto, volveremos a calcular dp[i] hasta dp[j - 1] y el valor del subsegmento [j;i].
Considere el siguiente problema simple: dada una matriz de enteros, debe dividirla en la cantidad mínima de subsegmentos que no se intersecan para que cada número se incluya en algún subsegmento y que cada subsegmento contenga los mismos números. Por ejemplo, para una matriz 1 2 2 3 3 3 2 1 1, la partición óptima se ve así: [1] [2 2] [3 3 3] [2] [1 1]. Esta tarea se resuelve fácilmente simplemente pasando por la matriz (ponemos todos los mismos elementos consecutivos en un subsegmento), pero lo resolveremos usando programación dinámica como ejemplo.
interno;
cin>> norte;
// llenar matriz con índice 1
vectorarr(n + 1);
para (int i = 1; i <= n; i++)
cin>> arri[yo];
// establecer inicialmente +oo en valores dp
vector dp(n + 1, 1000000000);
// una matriz de longitud cero no necesita dividirse, por lo que la respuesta es 0
pd[0] = 0;
// cuenta la respuesta para dp[i] en i ascendente
para (int i = 1; i <= n; i++) {
// actualmente arr[i] es el último elemento, por lo que será el número más a la derecha en el último subsegmento
// recorrer todas las opciones para saber dónde comenzó este último subsegmento
para (int j = i; j > 0; j--) {
if (arr[j] != arr[i]) {
// si encuentra un elemento que no es igual al último, entonces el subsegmento contendrá números diferentes, y esto no cumple la condición
// no tiene sentido continuar, porque desplazando el borde izquierdo a la izquierda, este elemento no desaparecerá, por lo que rompemos
romper;
}
// imagina que el último subsegmento fue [j;i]
// por lo que debe tomar la partición óptima de los primeros elementos j-1 y agregar 1 (el subsegmento [j; i] en sí)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
Si los elementos pueden no pertenecer a ninguno de los subsegmentos, solo debe considerar la opción adecuada, como dp[i] = dp[i - 1]