Programación Dinámica (DP: Dynamic Programming)
La programación dinámica es un tanto confusa, y lo sé! en las últimas semanas, estuve interrogando a muchas personas: "Qué es la programación dinámica?" muchas de ellas respondían conceptos muy confusos, por lo que llegué a concluír (erróneamente) que la programación dinámica era una especie de magia mediante la cual los algoritmos se hacen mucho más eficaces y rápidos, y que todo mago capaz de invocar el conjuro de la programación dinámica de forma exitosa, sería capaz de resolver todos los problemas de algoritmia del mundo.... no... DEL UNIVERSO!
Pero luego de un tiempo, y luego de que Jhtan me explicara varias veces el concepto (btw, gracias ^_^) por fin entendí qué es la programación dinámica:
NO ES MAGIA de hecho, nada es magia... todo tiene su explicación ;)
La programación dinámica tampoco es una forma de solucionar todos los problemas del universo y traer la felicidad y la paz mundial, de hecho, la programación dinámica también tiene sus limitaciones (como cualquier otro paradigma de algoritmia) y no funciona para cualquier problema... como ven, nada es mágico, y, en todo el conocimiento que he coleccionado a lo largo de mi vida, podría asegurarles casi con certeza: nada es mágico, no hay una receta mágica que funcione para todo y garantice perfección, si hacer algoritmos fuera algo automatizable, entonces habrían algoritmos para hacer algoritmos, y por lo tanto, programas que programen programas.
(Pero eso ya es un tema diferente...)
Si la programación dinámica no es magia, y si tampoco es una receta mágica, entonces... ¿Qué es exactamente la programación dinámica? y ¿por qué debería un informático entenderla? Vamos por pasos...
La programación dinámica es un paradigma (entre muchos) para resolver problemas. Este paradigma consiste en: utilizar resultados parciales (que el programa ha calculado y guardado en algún lugar) para dar con el resultado requerido. Un ejemplo! (bastante escueto e inútil, pero que ayudará a entender el paradigma): imagina que aún estás en colegio, y tu profesora quiere jugar un juego: ella te dirá una palabra que empieza con "a" y tú tienes que buscarla en el diccionario y leerle su significado... si tus compañeros encuentran la palabra antes que tú, ella te castigará sin recreo (digamos que está loca, y la lleva contra tí, o algo así), por suerte, tú eres más avispado que tus compañeros, y, como sabes que la profesora preguntará una palabra que comience con la letra "a", separas la sección del diccionario que contiene todas las palabras con la letra "a" y eso te da cierta ventaja.
En el ejemplo, la porción del diccionario que haz separado, constituye un conjunto de resultados parciales, y para encontrar el resultado, buscas entre los resultados parciales el resultado correcto. La programación dinámica se trata, básicamente, de eso: calcular resultados parciales, guardarlos, y luego usarlos (ya sea buscando entre ellos o realizando operaciones con ellos) para obtener el resultado deseado.
Viéndolo así, Gauss utilizó este paradigma para resolver el problema de 1 + 2 + 3 + ... + n y simplificarlo en su, tan conocida fórmula n(n+1)/2 cuando aún era niño.
Cuenta la anécdota que, el maestro de aritmética de Gauss le planteó al salón el problema de sumar los primeros 100 números de forma consecutiva (1 + 2 + 3 + ... + 100), pero Gauss se dio cuenta que 1+99 = 100 y que 2 + 98 = 100 y que r + ( 100 - r ) = 100 y por lo tanto r + (n - r) = n... y allí está de nuevo resultados parciales, Gauss encontró todos los resultados parciales, los guardó, y se dio cuenta que formaban un rectángulo, luego, se dio cuenta que el resultado deseado era uno de los triángulos contenido en el conjunto de resultados parciales, así que procesó todos estos resultados parciales para obtener el resultado deseado, y de allí viene su fórmula n(n+1)/2.
Ahora vamos a la siguiente pregunta...
Aunque la programación dinámica no es una receta mágica, es una de las muchas armas que todo informático debería saber empuñar. Hay una gran variedad de problemas que se pueden resolver con programación dinámica, uno de ellos es el de Longest Common Subsequence.
Y bueno, recién estoy entendiendo la programación dinámica y no tengo mucha experiencia en esto del competitive programming y por eso aún no entiendo del todo sus implicaciones...
Pero lo que sí puedo afirmarles con certeza es que, entender (al menos en parte) cómo funciona la programación dinámica, y ser capaz de identificar problemas que requieren de programación dinámica para su solución, me ha dado cierto aire de confianza, la sensación de que, todos los problemas a los que no les encuentro solución, TIENEN una solución, pero primero, necesito aprender una nueva forma de encararlos: de entenderlos.
Y por último, un consejo para entender la programación dinámica: el problema Maximum Sum, el sitio uHunt lo clasifica como un problema de nivel de dificultad 1 (bastante fácil) que se resuelve mediante programación dinámica. Es altamente recomendable resolverlo sin buscar ayuda, por eso, es mejor entenderlo resolviendo este algoritmo... será difícil al principio, pero a mí me funcionó. Solo intenten resolverlo mientras piensan una y otra vez "por qué necesito resultados parciales?" "cómo voy a usar resultados parciales para resolver este problema?"... esto me funcionó a mí... espero que también te funcione a tí ^ w ^
