¿Cómo identifica un problema como adecuado para la programación dinámica?

He estado leyendo sobre programación dinámica últimamente. Me gustaría saber de alguien que comenzó desde cero y ahora es bastante bueno para identificar y resolver problemas de DP. Me cuesta identificar estos problemas como DP y enmarcar una solución concisa.

He pasado por la mayoría de los problemas de DP para principiantes y los recursos del MIT, etc.

Vengo de un fondo de física, y por lo tanto, muchas matemáticas. Encuentro problemas fáciles de detectar que se adaptan bien a las soluciones de programación recursiva / dinámica al encontrar similitudes con la prueba por inducción .

En prueba por inducción tiene dos partes:

• demuestras que si algo es cierto para la iteración N, también es cierto para la iteración N + 1
• demuestras que es cierto para la iteración 1

En programación recursiva / programación dinámica:

• identifica una condición de salida (por ejemplo, conecta la solución para la iteración 1)
• calcula la solución para la iteración N dada la solución para la iteración N-1

Entonces, como respondieron otros, es una cuestión de experiencia y de captar las pistas, pero puedes reutilizar otras habilidades para guiarte. Después de eso, debe tener siempre las dos partes que mencioné: si no lo hace, entonces no funcionará.

Por ejemplo, para generar todas las permutaciones de un conjunto:

• condición de salida: si solo tiene un elemento, devuélvalo
• recursividad: las permutaciones de un conjunto de N elementos son los N conjuntos de permutaciones que obtienes al elegir cada elemento y combinarlos con todos los conjuntos N-1 de (muchas) permutaciones del subconjunto que obtienes al eliminar el elemento.

La mayoría de los problemas de programación dinámica se pueden resolver mediante la memorización. La memorización es normalmente más intuitiva y más fácil de codificar. Puede resultarle útil pensar en términos de memorización en lugar de DP.

Por lo general, es más fácil intuir si un problema es adecuado para la memorización (los pasos son los mismos que la respuesta de Slivvz , pero creo que el cambio mental es un poco más corto). Sin embargo, una vez que haya resuelto un problema mediante la memorización, puede examinar cómo se está llenando su caché de notas y luego llenarla en orden, sin recurrencia ... lo que cambia su algoritmo a un algoritmo de programación dinámico.

TL; DR; versión: puede resultarle más fácil comprender la programación dinámica en términos de memorización.

Consulte también StackOverflow: programación dinámica y memorización: enfoques ascendentes frente a descendentes .

La programación dinámica tiene dos definiciones:

1. Subestructura óptima
   Las soluciones más grandes pueden derivarse de soluciones más pequeñas; La resolución no es bidireccional.

2. Subproblemas superpuestos
   Las pequeñas soluciones se reutilizarán muchas veces. Si los subproblemas no se superponen en absoluto, entonces no se beneficiará de DP / memorización; lo que tienes es dividir y conquistar en su lugar.

El enfoque general para los problemas de DP es:

• Escriba una versión recursiva o iterativa ingenua que funcione.

• Tenga en cuenta que la función está haciendo trabajo redundante.

• Encuentre una manera de evitar hacer ese trabajo redundante, a menudo mediante la memorización.

Nunca había implementado un único solucionador de programación dinámica (mi experiencia es matemática / física / computación numérica aplicada, no CS) hasta hace unos años, cuando comencé a resolver los problemas del Proyecto Euler . Los problemas que se pueden resolver con DP allí (por ejemplo , 76 , 158 , 161 , 242, pero hay muchos más) resultó ser mi tipo favorito. Definitivamente mejorarás al detectar cuándo será una técnica útil: básicamente busca cosas que parezcan que podrían resolverse mediante algún tipo de enfoque recursivo, de dividir y conquistar, donde también es posible domar la explosión de caminos que necesitan para ser explorado reconociendo subproblemas recurrentes y reutilizando los resultados previamente calculados; poder identificar el vector de estado mínimo para memorizar, y qué "historia" irrelevante se puede borrar, es el paso crucial.