Un ejemplo simple para alguien que quiera comprender la programación dinámica [cerrado]

96

Estoy buscando un ejemplo comprensible para alguien que quiera aprender programación dinámica. Aquí hay buenas respuestas sobre qué es la programación dinámica . La secuencia de fibonacci es un gran ejemplo, pero es demasiado pequeña para arañar la superficie. Parece un gran tema para aprender, aunque todavía no he tomado la clase de algoritmos, espero que esté en mi lista para la primavera.

algorithm dynamic-programming AraK
fuente

Respuestas:

30

Consulte este sitio: Problemas de práctica de programación dinámica

Nick Dandoulakis
fuente
1
Ver esta conferencia del MIT video.mit.edu/watch/… y luego resolver los problemas anteriores, lo ayudaría a comprender por qué DP es útil.
pg2286
Por ejemplo, el enlace de YouTube en el comentario ya está roto. Nuevo enlace: youtube.com/watch?v=OQ5jsbhAv_M
AJP
Eche un vistazo a este conjunto de videos que encontré que cubre el aspecto de arriba hacia abajo y de abajo hacia arriba de los algoritmos de manera bastante intuitiva: youtube.com/playlist?list=PLx-Ye3Zw0WL0O_IDmbcVHlKqJuGEfw3VG
william007
Parece que el MIT movió su contenido de la página principal a la página MIT OpenCourseWare, por lo que el enlace @ pg2286 proporcionado no es válido. El enlace ahora es 19. Programación dinámica I La lista de reproducción completa Introducción a los algoritmos también está disponible
rite2hhh
7

La idea detrás de la programación dinámica es que estás almacenando en caché (memorizando) soluciones a subproblemas, aunque creo que hay más que eso.

Hay muchos problemas de Google Code Jam, por lo que las soluciones requieren una programación dinámica para ser eficientes. Ejemplos:

Bienvenido a Code Jam (moderado)

Hacer trampa con un árbol booleano (moderado)

PermRLE (difícil)

Tenga en cuenta que cada uno de los concursos de práctica de Code Jam tiene una sección de "Análisis del concurso" por si no está tratando de resolver el problema.

Joey Adams
fuente
Gracias por los recursos. Resuelvo una o dos preguntas del proyecto euler de vez en cuando, y parece que estoy realmente atascado en algunos problemas que necesitan conocimientos sobre DP.
AraK
5
  1. Geeks for geeks tiene una gran colección de problemas de programación dinámica. Creo que este conjunto es uno de los mejores si se está preparando para una entrevista.
  2. Si desea pequeños videos tutoriales sobre problemas de DP, puede consultar este conjunto de problemas del MIT.
Diptendu
fuente
4

Calcular distancias de Levenshtein fue uno de los primeros problemas que resolví con programación dinámica; Creo que es un próximo paso decente de la secuencia de Fibonacci en términos de complejidad.

http://en.wikipedia.org/wiki/Levenshtein_distance

David Winslow
fuente