No entiendo la programación dinámica. ¿Qué tengo que hacer?

Answer 1

Muchas gracias por la A2A.
La Programación Dinámica es básicamente un ARTE, como me gusta pensarlo. Siempre me sorprende cómo los programadores tienen solo unas pocas líneas de lógica que resuelven un problema tan grande y la respuesta siempre es la Programación Dinámica. Es uno de los temas más complicados de la programación competitiva y su capacidad para dominar requiere mucho tiempo, práctica y paciencia también. No soy un experto en esto, pero he resuelto problemas usando DP muchas veces, por lo que puedo ayudarlo con esto.

En primer lugar, simplemente relájate. Da un paso atrás y deja el tema por unos días. Dale un nuevo comienzo después de algún tiempo. Por lo menos, esto es lo que hice porque la expresión en mi cara era similar a esto cuando empecé con DP

Comencé a leer el código para el problema de la ruta más corta de una sola fuente, se explicó con el algoritmo Bellman Ford y se me explicó cómo dividirlo en sub problemas y todo. Pensé que todo estaba bien y luego leí el encabezado que decía “Implementación”. Lo que estaba escrito allí me sorprendió bastante. Era una relación de recurrencia de dos líneas, algo así.

F (u, v) = min (F (u, x) + w (x, u) para todas las x

y yo era como que demonios? Estaba en blanco porque no pude ver cómo una ecuación tan pequeña podría resolver un problema como este. Todo lo que me ayudó en este caso fue practicar y leer lo mismo de múltiples fuentes. Por lo tanto, recomendaría lo mismo para usted. Solo lea todo lo que pueda sobre programación dinámica y estará listo para comenzar.

************************* Recursos ************************ ********

• Tutorial de Programación Dinámica
• ¿Cuáles son los problemas de programación dinámica en la sesión de práctica?
• Tags – problemas | CodeChef
• Tutoriales de algoritmos
• Foros de TopCoder
• Estadísticas TopCoder – Archivo de problemas
• Programación dinámica desde CLRS
• Problemas en DP en SPOJ y Codeforces también.

Feliz codificacion !!!!!

Answer 2

La programación dinámica es un tema muy importante para la entrevista técnica y uno simplemente no puede descuidar el tema. Como cualquier problema de DS, la programación dinámica puede ser difícil solo si quieres que sea difícil. Si entiendes bien la recursión, puedes resolver los problemas de DP usando la Memoización, o puedes usar la Tabulación, que es de naturaleza iterativa.

Nadie espera que domines DP en un día o dos. Requiere tiempo y paciencia, pero lo más importante es que requiere confianza. Comience con los problemas básicos, entiéndalos primero y luego, después de sentirse cómodo, intente resolver los problemas por sí mismo sin mirar las soluciones propuestas. Yo recomendaría el siguiente enlace para problemas de DP. Buena suerte.

Archivos de DP – Techie Delight

Answer 3

El algoritmo funciona dividiendo un gran problema en estados de problemas más pequeños, resolviendo los estados de problemas anteriores y construyendo a partir de esto conduce a una eventual solución efectiva. La parte difícil no es “lo que es la programación dinámica”, es “¿Cómo puedo utilizar correctamente los principios de programación dinámica para resolver más rápidamente mi problema?” Además, no siempre es necesario si su problema es independiente de la velocidad. Sea paciente, y comience por resolver problemas más fáciles. Si basa sus quejas únicamente en el hecho de que no puede resolver problemas de programación dinámica, no sea tan duro con usted mismo. Para comprender la programación dinámica, primero debe comprender la recursividad, las optimizaciones básicas (cálculos iterativos, almacenamiento en caché, etc.).

Escuela de holberton

Answer 4

Comience con un problema básico de dp e intente avanzar desde técnicas de forma bruta hasta técnicas más avanzadas. Esto te ayudará a entender el rol de DP y lo que está optimizando.

Ejemplo, tomemos el problema de cambio de moneda. Notará que dados los valores predeterminados, puede resolverlo fácilmente mediante la creación de múltiples bucles for.

Ahora ocurre el problema, cuando tiene que tomar entradas para el número de monedas y la suma que se generará. El problema aquí es cómo crear bucles dinámicamente. Aquí entra en juego la técnica llamada recursión.

Una vez que haya hecho una solución utilizando la recursión, notará que se repiten muchos subcasos, así que ¿por qué no almacenarlos y reutilizarlos? Esto te llevará a una técnica llamada memorización. La implementación de esto en su solución le dará una solución de programación dinámica.

Una vez que trabaje paso a paso desde el algoritmo de fuerza bruta y descubra qué necesita para mejorarlo, comenzará a reconocer los patrones en los problemas y la mejor manera de resolverlos.

Answer 5

Déjame decirte algo:
Yo tampoco.

Sin embargo, sé cómo resolverlo. Al igual que cualquier otro concepto, tienes que practicar la implementación de la programación dinámica.

Hazlo por cien veces. O más. Vendrá a ti, y también a mí. No es diferente si en lugar de la programación dinámica es una programación codiciosa, o el infierno, incluso para los bucles.

Answer 6

Prueba esta serie de conferencias