2009-10-08 10 views
84

Busco un ejemplo manejable comprensible para alguien que quiera aprender la programación dinámica. There are nice answers here about what is dynamic programming. La secuencia de fibonacci es un gran ejemplo, pero es demasiado pequeña para rayar la superficie. Se ve un gran tema para aprender acerca aunque no he tomado la clase de algoritmos, sin embargo, es de esperar que está en mi lista para la primavera.Un ejemplo sencillo para alguien que quiera entender la programación dinámica

Respuesta

4

Cálculo de 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

28
+1

Al ver esta conferencia del MIT http://video.mit.edu/watch/introduction-to-algorithms-lecture-19-dynamic-programming-i-fibonacci-shortest-paths-14225/ y luego resolver los problemas anteriores , lo ayudaría a comprender por qué DP es útil. – user504879

+0

Mientras que este enlace puede responder a la pregunta, es mejor incluir las partes esenciales de la respuesta aquí y proporcionar el enlace de referencia. Las respuestas de solo enlace pueden dejar de ser válidas si la página vinculada cambia. - [crítica] (/ revisión/de baja calidad postes/17995545) – kometen

6

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

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

Welcome to Code Jam (moderate)

Cheating a Boolean Tree (moderate)

PermRLE (hard)

Note que cada uno de los concursos de práctica Code Jam tiene una sección "Análisis concurso" porque si no tienes ni idea tratar de resolver el problema.

+0

gracias por los recursos. Resuelvo una o dos preguntas de project euler de vez en cuando, y parece que estoy realmente atrapado en algunos problemas que necesitan conocimiento sobre DP. – AraK

5
  1. Frikis para frikis tiene una gran collection de problemas de programación dinámica. Siento que este set es uno de los mejores si te estás preparando para una entrevista.
  2. Si desea pequeños videos tutoriales sobre problemas de DP, puede consultar el problema this establecido en MIT.
Cuestiones relacionadas