¡Mirad! Voy a revelar el código de trucos para que salga ileso del otro lado, habiendo dominado a la bestia no domable, también conocida como programación dinámica. Esa es la manzana del conocimiento que desayunarás hoy.
O al menos eso es lo que pensaste cuando empezaste a leer esto, ¿verdad? O quizás estabas pensando, “¿quién es este tipo que incluso diría que intenta enseñar los secretos de ese método esotérico?”
En serio, soy un don nadie. Y definitivamente soy el tipo de persona que tendría una sonrisa en su rostro si el entrevistador o el Prof. in viva no piden nada de la programación dinámica.
Bueno, ya sabes lo que dicen. Los que no pueden, enseñan .
¿Aún conmigo? Tsk, tsk. Ya me siento mal por ti. Quiero decir, si ni siquiera pretendo dar un consejo en este momento, probablemente murmuren maldiciones, y tengo la sensación de que eso podría estropearme. karma.
Por lo tanto, la programación dinámica. ¿Recuerdas cuando dicen: ” Mira siempre el panorama general “? ¿O cuando alguien usa la frase ” No puedes ver el bosque para un árbol “? La Programación Dinámica es la versión de los programadores de mirar el panorama general.
Vamos a jugar un juego simple. Estás en un país extraño, y este solo tiene billetes de $ 5, $ 2, $ 1. Tienes que pagar $ 8 para salir de un atasco. Llamemos a eso una multa por exceso de velocidad. Y la ley no le permite elegir más billetes de los necesarios. Entonces, ¿cómo ganas $ 8? Sencillo. Usted comienza con el mayor valor de la factura que puede obtener. Eso es $ 5. ¿Ya son $ 8?
No, no es. Vamos a elegir otros $ 5 entonces. ¿Es $ 8 ahora? Técnicamente, han pasado los $ 8 y la señora en el mostrador del banco no le va a dar ningún cambio. Ella sonríe ante tus habilidades matemáticas.
Bien, si no $ 5, solo ve con la próxima factura de mayor valor. Eso es $ 2. Ahora tienes $ 7. ¿Es $ 8? Realmente no. Pero hay un billete de $ 1, así que puedes tirar uno de esos y pagar para salir de la situación.
En el siguiente país en su gira, aparece en otra tierra igualmente sospechosa y se metió en un problema similar. Tienes que pagar la misma multa de $ 8 nuevamente. Con el mínimo número posible de facturas.
Ahora tiene facturas de $ 5, $ 4, $ 1. Entonces, ¿qué haces para obtener $ 8? Usted comienza con el valor más alto de la factura que tiene: $ 5. Justo como antes. Solo necesita aportar $ 3 después de sacar $ 5 de su billetera. Caminas hacia el mostrador, le das a la dama esos 4 billetes, uno de $ 5 y otros tres billetes de $ 1. ¿Y ella qué hace? Ella se ríe de tus habilidades para contar y dice: “¿En serio? ¿Estás desperdiciando 4 billetes por $ 8? Puedes hacerlo mejor. Ahorra papel “.
Te confundes ¿Qué hay de malo en tu estrategia? Estás agregando lo que puedas en este momento. Suena razonable, ¿verdad? Para minimizar el número de billetes, está agregando el valor máximo o la denominación a la mezcla. Bueno, como resultado, puedes poner dos billetes de $ 4 y ahorrar un 50% en papel en el proceso.
Claramente, su estrategia inicial no fue universalmente cierta. Estabas haciendo tu mejor esfuerzo en este momento . Estabas viendo cuánto necesitas para alcanzar la meta y agregando lo mejor que pudieras. Pero, ¿qué deberías haber hecho en su lugar?
Deberías haber dado un paso atrás. Debería haber mirado todo lo que tiene, desde lo mejor que puede hacer hasta lo peor que puede hacer. Y luego tomó una decisión, con la imagen más grande en su mente.
Eso es programación dinámica para ti. Siempre recuerda lo que tienes. Haga que todos sus activos sean parte de la ecuación. ¡Probablemente ya lo sabías! En ese caso, por favor, no me maten por tratarlo como un noob durante tanto tiempo.
Es un concepto de aplicación general. Cuando se necesita reducir la complejidad de tiempo (tiempo necesario para completar una ejecución en función del tamaño de entrada), se debe aumentar la complejidad de espacio (memoria ocupada para completar una ejecución en función del tamaño de entrada). [Sí, lo sé. Solo estás ansioso por comentar y frotarme en mi cara, citando contra-ejemplos de donde eso no es verdad, ¿no es así? ¡Adelante, comenta!]
Eso es lo que haces en un problema de programación dinámica. En lugar de elegir a ciegas lo mejor en cada etapa, mantienes una mesa. Y use esa tabla para comparar entre algunas opciones posibles, que son un poco complicadas que elegir el mejor en este momento. Usted agrega el mejor valor posible obtenido por este método.
Entonces, ¿de dónde obtienes buenos recursos para aprender esto? Comience con el libro CLRS. Intente resolver problemas clásicos de DP como EDITAR DISTANCIA o LA SUBSECUENCIA MÁS LARGA. Y por resolver, quiero decir, tomar algunos datos de muestra, codificar en una solución en un idioma que conozca, ejecutar algunos casos de prueba.
No voy a entrar en todas esas teorías de estructuras subóptimas. Sólo lee esa mierda. Y tome un lápiz y papel, asuma algunos casos de uso, elabore algunos ejemplos a mano con valores de muestra. Tus conceptos estarían mejor grabados en tu memoria.
Ahora, vaya a http://www.geeksforgeeks.org y vea cómo resolvieron los problemas de programación dinámica. Tienen una buena colección de problemas de programación dinámica estándar. No mires las soluciones al principio. Intenta codificarlos por tu cuenta. Sí, todos dicen eso! Pero eres sincero con el aprendizaje, y el código secreto de trucos es que si intentas honestamente sin mirar la solución al principio, te beneficiará mucho. Luego revise los comentarios también, para una solución alternativa para el mismo problema.
A continuación, pruebe los tutoriales de TopCoder. Intente resolver problemas de DP similares del juez en línea de Esfera (SPOJ), la competencia de programación, el concurso de programación, la programación de computadoras en línea, HackerRank, etc. sitios de codificación competitivos. Scourge Google para preguntas de DP en entrevistas.
Y cuando dije intentarlo, me refería al tipo de intento sólido de Yoda, es decir, hacer o no, no hay intento. Si después de todo esto todavía no confía en la programación dinámica, hágamelo saber.