Programación dinámica es un método utilizado en matemáticas e informática para resolver problemas complejos dividiéndolos en subproblemas más simples. Al resolver cada subproblema una sola vez y almacenar los resultados, se evitan cálculos redundantes, lo que conduce a soluciones más eficientes para una amplia gama de problemas. Este artículo proporciona una exploración detallada de los conceptos de programación dinámica, ilustrada con ejemplos.

que significa xd

Programación dinámica

Tabla de contenidos

• ¿Qué es la programación dinámica?
• ¿Cómo funciona la programación dinámica?
• Ejemplos de programación dinámica
• ¿Cuándo utilizar la programación dinámica?
• Enfoques de programación dinámica
• Algoritmo de programación dinámica
• Ventajas de la programación dinámica
• Aplicaciones de la programación dinámica
• Aprenda los conceptos básicos de la programación dinámica
• Conceptos avanzados en programación dinámica
• Problemas de programación dinámica

¿Qué es la programación dinámica (DP)?

Programación dinámica (DP) es un método utilizado en matemáticas e informática para resolver problemas complejos dividiéndolos en subproblemas más simples. Al resolver cada subproblema una sola vez y almacenar los resultados, se evitan cálculos redundantes, lo que conduce a soluciones más eficientes para una amplia gama de problemas.

¿Cómo funciona la programación dinámica (DP)?

• Identificar subproblemas: Divida el problema principal en subproblemas más pequeños e independientes.
• Soluciones de tienda: Resuelva cada subproblema y almacene la solución en una tabla o matriz.
• Soluciones de construcción: Utilice las soluciones almacenadas para desarrollar la solución al problema principal.
• Evite la redundancia: Al almacenar soluciones, DP garantiza que cada subproblema se resuelva solo una vez, lo que reduce el tiempo de cálculo.

Ejemplos de programación dinámica (DP)

Ejemplo 1: Considere el problema de encontrar la secuencia de Fibonacci:

Secuencia Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Enfoque de fuerza bruta:

Para encontrar el enésimo número de Fibonacci usando un enfoque de fuerza bruta, simplemente sumarías el (n-1)ésimo y (n-2)ésimo Números de Fibonacci. Esto funcionaría, pero sería ineficaz para valores grandes de norte , ya que requeriría calcular todos los números de Fibonacci anteriores.

Enfoque de programación dinámica:

Serie de Fibonacci usando programación dinámica

• Subproblems: F(0), F(1), F(2), F(3), …
• Soluciones de tienda: Cree una tabla para almacenar los valores de F(n) a medida que se calculan.
• Soluciones de construcción: Para F(n), busque F(n-1) y F(n-2) en la tabla y agréguelos.
• Evite la redundancia: La tabla garantiza que cada subproblema (por ejemplo, F(2)) se resuelva sólo una vez.

Al usar DP, podemos calcular eficientemente la secuencia de Fibonacci sin tener que volver a calcular los subproblemas.

cómo inyectar una clase abstracta simulada

Ejemplo 2: Subsecuencia común más larga (encontrar la subsecuencia más larga que sea común a dos cadenas)

Ejemplo 3: Ruta más corta en un gráfico (encontrar la ruta más corta entre dos nodos en un gráfico)

Ejemplo 4: Problema de mochila (encontrar el valor máximo de artículos que se pueden colocar en una mochila con una capacidad determinada)

¿Cuándo utilizar la programación dinámica (DP)?

La programación dinámica es una técnica de optimización utilizada a la hora de resolver problemas que consta de las siguientes características:

1. Subestructura óptima:

Subestructura óptima significa que combinamos los resultados óptimos de los subproblemas para lograr el resultado óptimo del problema mayor.

C#

Ejemplo:

Considere el problema de encontrar el costo minimo ruta en un gráfico ponderado desde un fuente nodo a un destino nodo. Podemos dividir este problema en subproblemas más pequeños:

• Encuentra el mínimo costo camino desde el fuente nodo para cada uno intermedio nodo.
• Encuentra el mínimo costo camino de cada uno intermedio nodo al destino nodo.

La solución al problema mayor (encontrar la ruta de costo mínimo desde el nodo de origen al nodo de destino) se puede construir a partir de las soluciones a estos subproblemas más pequeños.

2. Subproblemas superpuestos:

Los mismos subproblemas se resuelven repetidamente en diferentes partes del problema.

Ejemplo:

Considere el problema de calcular el serie de fibonacci . Para calcular el número de Fibonacci en el índice norte , necesitamos calcular los números de Fibonacci en índices n-1 y n-2 . Esto significa que el subproblema de calcular el número de Fibonacci en el índice n-1 se utiliza dos veces en la solución al problema más amplio de calcular el número de Fibonacci en el índice norte .

Enfoques de programación dinámica (DP)

La programación dinámica se puede lograr mediante dos enfoques:

1. Enfoque de arriba hacia abajo (memorización):

En el enfoque de arriba hacia abajo, también conocido como memorización , comenzamos con la solución final y la dividimos recursivamente en subproblemas más pequeños. Para evitar cálculos redundantes, almacenamos los resultados de los subproblemas resueltos en una tabla de memorización.

Analicemos el enfoque de arriba hacia abajo:

• Comienza con la solución final y la divide de forma recursiva en subproblemas más pequeños.
• Almacena las soluciones a los subproblemas en una tabla para evitar cálculos redundantes.
• Adecuado cuando el número de subproblemas es grande y muchos de ellos se reutilizan.

2. Enfoque ascendente (tabulación):

En el enfoque ascendente, también conocido como tabulación , comenzamos con los subproblemas más pequeños y gradualmente llegamos a la solución final. Almacenamos los resultados de los subproblemas resueltos en una tabla para evitar cálculos redundantes.

Analicemos el enfoque ascendente:

• Comienza con los subproblemas más pequeños y avanza gradualmente hasta la solución final.
• Llena una tabla con soluciones a subproblemas de abajo hacia arriba.
• Adecuado cuando el número de subproblemas es pequeño y la solución óptima se puede calcular directamente a partir de las soluciones a subproblemas más pequeños.

Programación dinámica (DP) Algoritmo

La programación dinámica es una técnica algorítmica que resuelve problemas complejos dividiéndolos en subproblemas más pequeños y almacenando sus soluciones para uso futuro. Es particularmente eficaz para problemas que contienen subproblemas superpuestos y subestructura óptima.

Algoritmos comunes que utilizan programación dinámica:

• Subsecuencia común más larga (LCS): Encuentra la subsecuencia común más larga entre dos cadenas.
• Ruta más corta en un gráfico: Encuentra el camino más corto entre dos nodos en un gráfico.
• Problema de mochila: Determina el valor máximo de artículos que se pueden colocar en una mochila con una capacidad determinada.
• Multiplicación de cadenas de matrices: Optimiza el orden de multiplicación de matrices para minimizar el número de operaciones.
• Secuencia Fibonacci: Calcula el enésimo número de Fibonacci.

Ventajas de la programación dinámica (DP)

La programación dinámica tiene una amplia gama de ventajas, que incluyen:

• Evita volver a calcular los mismos subproblemas varias veces, lo que genera importantes ahorros de tiempo.
• Garantiza que se encuentre la solución óptima considerando todas las combinaciones posibles.
• Divide problemas complejos en subproblemas más pequeños y manejables.

Aplicaciones de la programación dinámica (DP)

La programación dinámica tiene una amplia gama de aplicaciones, que incluyen:

• Mejoramiento: Problema de mochila, problema de camino más corto, problema de subarreglo máximo
• Ciencias de la Computación: Subsecuencia común más larga, distancia de edición, coincidencia de cadenas
• La investigación de operaciones: Gestión de inventario, programación, asignación de recursos.

Ahora, exploremos una hoja de ruta integral para dominar la programación dinámica.

programación por turnos

Aprenda los conceptos básicos de la programación dinámica (DP)

• ¿Qué es la memorización? Un tutorial completo
• Tabulación vs Memoización
• Propiedad óptima de la subestructura
• Propiedad de subproblemas superpuestos
• ¿Cómo resolver un problema de programación dinámica?

• Números de Fibonacci
• enésimo número catalán
• Números de campana (Número de formas de particionar un conjunto)
• Coeficiente binomial
• problema de cambio de moneda
• Problema de suma de subconjuntos
• Calcular nCr % p
• Cortar una varilla
• Algoritmo de valla de pintura
• Subsecuencia común más larga
• Subsecuencia creciente más larga
• Subsecuencia más larga tal que la diferencia entre adyacentes sea uno
• Submatriz cuadrada de tamaño máximo con todos los 1
• Ruta de costo mínimo
• Número mínimo de saltos para llegar al final.
• Subcadena común más larga (solución DP optimizada para el espacio)
• Cuente las formas de llegar a la enésima escalera usando el paso 1, 2 o 3
• Cuente todas las rutas posibles desde la parte superior izquierda hasta la parte inferior derecha de una matriz mXn
• Caminos únicos en una cuadrícula con obstáculos

2. Problemas medios de programación dinámica (DP)

• Algoritmo de Floyd Warshall
• Algoritmo de Bellman-Ford
• 0-1 Problema de mochila
• Impresión de artículos en mochila 0/1
• Mochila ilimitada (Se permite repetición de artículos)
• Rompecabezas de caída de huevos
• Problema de ruptura de palabras
• Problema de cobertura de vértice
• Problema de apilamiento de azulejos
• Problema de apilamiento de cajas
• Problema de partición
• Problema del viajante | Conjunto 1 (Programación ingenua y dinámica)
• La subsecuencia palindrómica más larga
• Subsecuencia creciente común más larga (LCS + LIS)
• Encuentre todas las sumas de subconjuntos (o subsecuencias) distintos de una matriz
• Programación de trabajo ponderada
• Count Derangements (Permutación tal que ningún elemento aparece en su posición original)
• Inserciones mínimas para formar un palíndromo.
• Coincidencia de patrones comodín
• Formas de organizar bolas de modo que las bolas adyacentes sean de diferentes tipos

3. Problemas difíciles de programación dinámica (DP)

• Partición palíndromo
• Problema de ajuste de palabras
• El problema de la partición del pintor
• Programa para problema de puente y antorcha.
• Multiplicación de cadenas de matrices
• Impresión de corchetes en el problema de multiplicación de cadenas de matrices
• Rectángulo de suma máxima en una matriz 2D
• Beneficio máximo comprando y vendiendo una acción como máximo k veces
• Costo mínimo para ordenar cadenas usando operaciones de inversión de diferentes costos
• Recuento de subsecuencias AP (progresión aritmética) en una matriz
• Introducción a la programación dinámica en árboles
• Altura máxima del árbol cuando cualquier nodo puede considerarse raíz
• Subcadena repetida y no superpuesta más larga

Enlaces rápidos:

• Aprenda la estructura de datos y los algoritmos | Tutorial de DSA
• Las 20 preguntas principales de la entrevista sobre programación dinámica
• 'Problemas de práctica' sobre programación dinámica
• 'Quiz' sobre programación dinámica