Patrones en Programación Dinámica - 2

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 un problema le pide que destruya/colapse/fusione (o similar) de manera óptima una matriz, entonces debe intentar resolverlo usando programación dinámica en subsegmentos.

Obtengamos dp[l][r] - la respuesta óptima para un subsegmento con índices de l a r. El recálculo de la dinámica depende en gran medida de la tarea, pero existen las siguientes ideas generales:

1) Mira los elementos extremos l y r. Si coinciden o se complementan de alguna otra manera, lo más probable es que sea posible actualizar el valor de dp[l][r] a través de dp[l+1][r-1]. De lo contrario, a través de dp[l][r-1] o dp[l+1[r].

2) A menudo sucede que el segmento [l;r] no se puede representar a través de una sola construcción. Entonces es necesario considerar todas las secciones posibles de este subsegmento en dos partes, es decir, iterar sobre el elemento k de l a r-1 y recalcular dp[l][r] hasta dp[l][k] y dp[ k+1][r] . En subsegmentos más pequeños, estas secciones también se clasificaron, por lo que, de hecho, se tienen en cuenta las opciones para dividir el subsegmento [l;r] no solo en dos partes, sino en cualquier número de ellas.
 

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 necesita verificar la existencia de una permutación en un problema, o encontrar el número de permutaciones que coinciden, o algo similar, entonces debería considerar usar la programación dinámica de subconjuntos.

El parámetro principal será una máscara de bits, que mostrará qué elementos ya se han incluido en la permutación y cuáles no. También suele ser necesario un segundo parámetro que indique qué elemento se incluyó en último lugar.

A menudo, las permutaciones se pueden ver en el contexto de las rutas en los gráficos. En consecuencia, consideremos un ejemplo clásico: el problema del camino hamiltoniano.
Un camino hamiltoniano es un camino simple que pasa por cada vértice del gráfico exactamente una vez. Se puede representar simplemente como una permutación de longitud n, donde n es el número de vértices. El orden dentro de esta permutación indicará el orden en que se recorren los vértices de este camino.

Para verificar la presencia de un camino hamiltoniano en el gráfico, comencemos con la dinámica dp[máscara][último]: ¿hay un camino simple que pase por alto los vértices marcados con unos en la máscara de bits y termine en el último vértice?
Los valores iniciales serán dp[2ⁱ][i] = verdadero, el resto falso, lo que significa que siempre hay un camino vacío que comienza en cualquiera de los vértices.
Teniendo el valor true en dp[mask][last] haremos transiciones hacia adelante, en el sentido de "extender el camino". Es decir, buscaremos el número de vértices que están marcados con cero en la máscara (aún no los hemos visitado en el camino) y al mismo tiempo tal que haya una arista desde el último hasta este vértice (el camino debe extenderse por un borde existente). Es decir, hacemos dp[mask | 2^k][k] = verdadero si dp[máscara][último] = verdadero Y máscara & 2^k = 0 (el vértice k aún no ha sido visitado) Y hay una última arista -> k.
En última instancia, existe una ruta hamiltoniana si hay un valor verdadero en dp para los parámetros de la máscara de bits de todos unos y cualquier último vértice.