Definición
La programación dinámica (DP) es un método para resolver un problema complejo dividiéndolo en una colección de subproblemas más simples, resolviendo cada uno de esos subproblemas una sola vez y almacenando sus soluciones
Fuente de la imagen: Todo sobre programación dinámica – Codeforces
Propiedades de DP
Cada problema DP tiene las siguientes dos propiedades:
- Subproblemas superpuestos : una solución óptima para una instancia contiene una solución óptima para sus subinstancias.
DP se utiliza principalmente cuando se necesitan soluciones de los mismos subproblemas una y otra vez. Si tomamos el ejemplo del siguiente programa recursivo para los números de Fibonacci , hay muchos subproblemas que se resuelven una y otra vez.
int fib (int n)
{
si (n <= 1)
return ((n == 1)? 1: 0);
retorno fib (n-1) + fib (n-2);
}
- Subestructura óptima : una solución recursiva contiene un número “pequeño” de subproblemas distintos (repetidos muchas veces).
Un problema dado tiene una propiedad de subestructura óptima si se puede obtener una solución óptima del problema dado usando soluciones óptimas de sus subproblemas. Por ejemplo, el problema del camino más corto.
Nota: Los números representan la longitud de la ruta, las líneas rectas indican bordes individuales. Fuente de la imagen: Subestructura óptima – Wikipedia
Aprender DP
Algunos buenos recursos para comenzar con la programación dinámica son:
- Programación dinámica: de principiante a avanzado – TopCoder
- Todo sobre la programación dinámica – Codeforces
- Tutorial para programación dinámica – Codechef
- Capítulo 15 – Programación dinámica – CLRS
- Programación dinámica – GeeksforGeeks
- Introducción a la programación dinámica – HackerEarth
- ¿Cuál es la diferencia entre la memorización y la programación dinámica? – StackOverflow
- Programación y memorización dinámicas: enfoques ascendentes frente a descendentes – StackOverflow
Algunos problemas estándar de DP son:
- Números de Fibonacci
- Problema de intercambio de monedas
- Problema de corte de varilla
- Subcadena común más larga
- Subsecuencia creciente más larga
- Coeficiente binomial
- Multiplicación de cadena matricial
- 0-1 Problema de mochila
- Árbol de búsqueda binario óptimo
- Subarray contiguo de suma más grande (algoritmo de Kadane)
Videos
Practica DP
Una vez que haya entendido los conceptos, pruebe sus conocimientos de DP en algunas de estas plataformas (al menos dos):
- Programación dinámica – Juez A2 en línea ( preferido )
- Programación dinámica – TopCoder
- Programación dinámica – Juez Esfera en línea (SPOJ)
- Programación dinámica – HackerEarth
- Programación dinámica – LeetCode
- Programación dinámica – InterviewBit
- Programación dinámica – HackerRank
- CodeMonk DP – HackerEarth
Maestro dp
En resumen, no hay fórmula ni truco ni atajo ni ninguna ciencia espacial para dominar el DP. La única forma de dominar DP es siguiendo este ciclo de vida:
Aprender
Práctica
Repetir
Además de la práctica fuera de línea, participe en concursos de programación competitivos celebrados en TopCoder, Codeforces, Codechef, HackerRank o Hacker Earth.
Maestros en este campo
¡Aquí hay algunos (¡no todos!) De los programadores que han dejado su huella en la Comunidad de Programación Competitiva especialmente en DP ( sí, son maestros en DP )
- Michal Danilák
- ¿Cuál fue la estrategia de programación competitiva de Anudeep Nekkanti para convertirse en el puesto 35 en el ranking mundial, en solo 6-7 meses?
- Sesión de preguntas y respuestas con Sumeet Varma
- ¿Cómo hizo Ashish Kedia para dominar la programación dinámica?
- Algorithms Weekly por Petr Mitrichev
- Gennady Korotkevich – Wikipedia (mi favorito :))
