¿Cuál es el mejor truco en la programación dinámica?

Answer 1

Ya mencioné un problema difícil que me gusta aquí: la respuesta de Michal Forišek a ¿Cuál es tu problema de programación dinámica favorito?
pero para esta pregunta escogeré otro truco: el truco que fue publicado por primera vez por Dan Hirschberg en 1975.

Este truco se aplicó por primera vez a una clase de problemas de DP relacionados que incluye el cálculo de la distancia Levensthein de dos cadenas, la subsecuencia más larga común de dos secuencias y la alineación óptima de secuencias de ADN. En todos los casos, la instancia son dos objetos de longitud m y n , y el DP se ejecuta en tiempo O (mn) : los estados del DP son todos pares (un prefijo del primer objeto, un prefijo del segundo objeto).

Ya se sabe que la implementación de DP de abajo hacia arriba (iterativa) nos permite ahorrar espacio: el valor de la solución óptima (por ejemplo, la longitud de la subsecuencia común más larga) se puede calcular en tiempo O (mn) mientras solo utilizando O (min (m, n)) espacio: para calcular la siguiente fila de la tabla DP, solo necesitamos recordar una fila anterior. Sin embargo, en realidad , la reconstrucción de una solución óptima parecía requerir tanto O (mn) tiempo y espacio, ya que aparentemente se necesita la tabla completa.

Aquí es donde entra en juego el truco de Hirschberg. Hirschberg ideó una forma inteligente de reconstruir una solución óptima en el mismo tiempo y espacio asintóticos que la solución que solo calculó su valor, es decir, en tiempo O (mn) y O (min (m) n)) espacio.

¿El truco? Usa divide y vencerás para reconstruir la solución. En la primera iteración, encuentre el punto donde la solución óptima cruza la fila central de la tabla DP. Luego, resuelva recursivamente dos problemas más pequeños, cada uno con aproximadamente la mitad de las filas. El punto aquí es que, independientemente de donde la solución óptima cruce la fila del medio, los dos problemas más pequeños juntos tendrán un tamaño aproximadamente igual a la mitad del tamaño del problema original. (Aquí, tamaño del problema = área de la tabla que debemos completar). Por lo tanto, todo el árbol de llamadas y ejecuciones recursivas del algoritmo solo será aproximadamente el doble de lento que el algoritmo original que solo era capaz de calcular el valor.

Para obtener una explicación más detallada y detallada, visite http://www.bioinformaticsonline…. , especialmente la Figura S3.3 que ilustra cómo la construcción de la solución completa se divide en dos subproblemas más pequeños.

Answer 2

Programación dinámica en enteros.

Es una idea muy agradable y elegante resolver problemas como: dados dos enteros [math] A [/ math] y [math] B [/ math] (puede que no se ajusten al tipo de datos de 64 bits), encuentre el número de enteros [ math] X [/ math] con [math] A ≤ X ≤ B [/ math], que tienen cierta propiedad.
Para este tipo de problemas, la mejor explicación es, de hecho, esta de Niklas B. (niklasb en CodeForces): DP en enteros
Hay muchos buenos problemas en CodeChef, de SPOJ, puedo recordar dos problemas: RAONE y GONE.

Answer 3

La optimización de Knuth.

Un truco dinámico de programación extremadamente útil pero sorprendentemente simple. Reduce la complejidad del tiempo de la construcción del árbol de búsqueda binaria óptima de [math] O (N ^ 3) [/ math] a [math] O (N ^ 2) [/ math].

La idea subyacente es breve: el índice de raíz óptimo de una matriz generalmente aumenta monótonamente con la longitud de la matriz. Entonces, si [math] K [/ math] es el índice de raíz óptimo de la matriz [math] A [0,…, n] [/ math] y [math] K_ {1}, K_ {2} [/ math] son índices radiculares óptimos de subgrupos [math] A [0,…, n-1] [/ math] y [math] A [1,…, n] [/ math] respectivamente, luego la condición [math] K_ {1} \ le K \ le K_ {2} [/ math] tiene que ser verdadero.

Esto también se puede utilizar para resolver otros problemas similares. Para más detalles, lea la solución explicada aquí para este problema.

Answer 4

Optimización del casco convexo. No está directamente relacionado con la geometría, sino que se inspira en ella. Creo que es muy genial.

El truco del casco convexo es una técnica (quizás mejor clasificada como una estructura de datos) utilizada para determinar de manera eficiente , después del preprocesamiento, qué miembro de un conjunto de funciones lineales en una variable alcanza un valor extremo para un valor dado de la variable independiente. Tiene poco que ver con los algoritmos de casco convexo.

Truco de casco convexo

Answer 5

Uso de la inducción hacia atrás en el juego pirata teórico del juego. No es exactamente una respuesta a su pregunta, sino un ejemplo de uso de DP para obtener un resultado altamente intuitivo (al menos en mi opinión).

Answer 6

No creo que haya un truco real para dominar la programación dinámica, pero si pudiera dar un consejo, sería:

1. Imagina las transiciones de estado de antemano.

Inmediatamente después de reconocer que un problema se puede resolver con la programación dinámica, dependiendo del nivel difícil del problema, no es fácil encontrar un estado de ajuste de memoria fácilmente, pero, si se imagina cómo sucederían las transiciones, entonces puede comenzar a calcular. qué información realmente importa ser representada como un estado y cuál puede ser descartada.

Answer 7

Me encantó este problema en el que se nos da un conjunto de pulsaciones de teclas: Imprima A, Ctrl A, Ctrl C y Ctrl-V, y debe encontrar el número máximo de A que puede imprimir.

Resolver la relación de recurrencia en sí fue complicado, pero una vez que llegue con la ayuda de algunos ejemplos (intenté 1 – 12), puede obtener fácilmente la solución O (n ^ 2). Luego, con algunos ejemplos de casos de prueba, descubrí una solución O (n), que fue muy satisfactoria. Aquí está el enlace a la solución que tengo: Programación dinámica: número máximo de A con las teclas Ctrl-A, Ctrl-C, Ctrl-V (pregunta de entrevista de Google)