¿Qué problemas comunes se resuelven con la programación dinámica?

Una lista de problemas comunes con soluciones de video está disponible en esta página de clase de algoritmos MIT ( http://people.csail.mit.edu/bdea …). Los problemas comunes incluyen:

• Subsecuencia contigua de valor máximo: dada una secuencia de n números reales A (1) … A (n), determine una subsecuencia contigua A (i) … A (j) para la cual se maximiza la suma de elementos en la subsecuencia.
• Hacer cambios: dados n tipos de denominaciones de monedas de valores v (1)
• Subsecuencia creciente más larga: Dada una secuencia de n números reales A (1) … A (n), determine una subsecuencia (no necesariamente contigua) de longitud máxima en la que los valores en la subsecuencia forman una secuencia estrictamente creciente.
• El Problema de la Navaja Entera: Dados n ítems, cada uno con el tamaño s (i) y el valor v (i), determinan el valor máximo que puede almacenarse en una morralla de tamaño C o menor.
• Partición equilibrada: dado un conjunto de n enteros, cada uno en el rango 0 … K, divida los enteros en dos subconjuntos para minimizar | S1 – S2 |, donde S1 y S2 denotan las sumas de los elementos en cada uno de los dos subconjuntos.
• Distancia de edición: Dadas dos cadenas de texto A de longitud n y B de longitud m, determine la distancia de edición para transformar A a B.

La programación dinámica es una de las mejores cosas cuando practicas preguntas de programación dinámica. Inicialmente, comience con algunos problemas estándar básicos de DP (programación dinámica) como problema de mochila 0/1, corte de varilla, multiplicación de matriz, etc. Y luego comience a codificar algunas preguntas fáciles de DP en varios sitios competitivos.

La mejor fuente para aprender el concepto de programación dinámica sería del libro: “Introducción a los algoritmos de Thomas Cormen”. El concepto de DP se explica de muy buena manera junto con el algoritmo de problemas DP estándar y el método de pensar para obtener ese DP algo de manera paso a paso.

También puede consultar Algoritmos: GeeksforGeeks. Después de aprender el concepto de DP y el algoritmo de lectura de algunos problemas estándar y comprenderlos, lea el enunciado del problema de los problemas dados en geeksforgeeks e intente encontrar una solución. Después de encontrar una solución o no obtener la solución después de intentarlo, vea la solución del problema dado. Esto ayudará a comprender más DP.

Estos son algunos de los problemas DP más frecuentes con las soluciones proporcionadas:

Subsecuencia común más larga | Introducción y longitud de LCS
Subsecuencia común más larga | Versión optimizada para espacio
Subsecuencia común más larga de secuencias K
Subsecuencia común más larga | Encontrar todos los LCS
El problema de subcadena común más largo
La subsecuencia palindrómica más larga usando programación dinámica
Problema de subsecuencia repetida más larga
Supersecuencia común más corta | Introducción y longitud SCS
Supersecuencia común más corta | Encontrar todos los SCS
Supersecuencia común más corta | Usando LCS
Subsecuencia creciente más larga usando programación dinámica
Subsecuencia bitónica más larga
Subsecuencia creciente con suma máxima
El problema de la distancia de Levenshtein (Editar distancia)
Encuentre el tamaño de la submatriz cuadrada más grande de 1 presente en una matriz binaria dada
Multiplicación de cadena matricial
Encuentre el costo mínimo para llegar a la última celda de la matriz desde su primera celda
Encuentra la secuencia más larga formada por números adyacentes en la matriz
Cuente el número de rutas en una matriz con un costo dado para llegar a la celda de destino
0-1 problema de mochila
Maximizar el valor de la expresión A [s] – A [r] + A [q] – A [p] donde s> r> q> p
Problema de partición
Problema de suma de subconjunto
Problema de partición de suma mínima
Encuentra todas las cadenas binarias de N dígitos sin ningún 1 consecutivo
Corte de varilla
Máximo corte de varilla de producto
Problema de cambio de monedas (suministro ilimitado de monedas)
Problema de cambio de moneda: encuentre el número total de formas de obtener la denominación de monedas
La subsecuencia alterna más larga
Cuente el número de veces que aparece un patrón en una cadena dada como una subsecuencia
Recoge los puntos máximos en una matriz satisfaciendo restricciones dadas
Cuente el total de combinaciones posibles de números de N dígitos en un teclado móvil
Encuentre el costo óptimo para construir un árbol de búsqueda binario
Word Break Problem
Coincidencia de patrones comodín

Encuentre la probabilidad de que una persona esté viva después de dar N pasos en la isla
Calcular la suma de todos los elementos en una submatriz en tiempo constante
Encontrar la suma máxima de la submatriz K x K en una matriz M x N dada
Encuentra la submatriz de suma máxima presente en una matriz dada
Encuentra la suma máxima de subsecuencia sin elementos adyacentes
Problema de submatriz máxima (algoritmo de Kadane)
Senderos más cortos de una sola fuente: algoritmo Bellman Ford
Caminos más cortos de todos los pares – Algoritmo de Floyd Warshall

Los rasgos clásicos de “subestructura óptima” y “subproblemas superpuestos”. Básicamente, si puede expresar la solución de un problema en términos de una versión más pequeña del mismo problema, tiene subproblemas superpuestos . Si la solución óptima para el problema más grande es una extensión de la solución óptima para los subproblemas más pequeños, tiene una subestructura óptima . DP se presta bien a los lenguajes funcionales y de recursión que optimizan las llamadas de cola. Debido a la naturaleza superpuesta de los problemas, a menudo es útil usar la memorización para evitar el doble cálculo, pero esto se suma a la sobrecarga de memoria de los algoritmos DP.

La programación dinámica se usa cuando puede escribir una fórmula recursiva para responder al problema y la fórmula recursiva exhibe subproblemas superpuestos.

Decimos que hay subproblemas superpuestos si la función recursiva se llama con los mismos argumentos varias veces durante el curso de la evaluación. Si imagina un árbol de todas las llamadas recursivas realizadas durante la evaluación, hay subproblemas superpuestos si alguno de los nodos es idéntico (son llamadas de función con argumentos idénticos). La programación dinámica funciona almacenando en caché los resultados de los valores previamente calculados de la función para que la función nunca se evalúe dos veces para los mismos argumentos.

Lo anterior es una descripción de la programación dinámica de arriba hacia abajo (“recursión con memorización”), pero la programación dinámica de abajo hacia arriba es el mismo principio, excepto que usted da el paso adicional de optimizar la recursión por completo al elegir un orden inteligente en el que Todos los valores de la función deben calcularse.

Para los programas que no involucran recursión, programas donde la recursión se usa simplemente para el flujo de control, o programas donde hay recursión pero no hay subproblemas superpuestos, no tiene sentido usar programación dinámica.

La programación dinámica básicamente utiliza la idea de dividir y conquistar en el espacio de solución de un problema. Básicamente, para cualquier problema [matemática] f (x), x \ en S [/ matemática] con un espacio de solución finita [matemática] S [/ matemática]. podemos proporcionar una solución de programación dinámica que divida el espacio de la solución en [matemática] S – [/ matemática] {[matemática] a [/ matemática]} y {[matemática] a [/ matemática]}. Donde [math] a [/ math] es una solución única en un conjunto de soluciones finitas S.

Sin embargo, la programación dinámica no puede resolver problemas que tienen un espacio de solución infinito o que no son computables para Turing (por ejemplo, detener el problema, que es decidir, dado un programa de computadora arbitrario y una entrada, si el programa terminará de ejecutarse o continuará ejecutándose para siempre).

El resultado final se basa en el subproblema, lo que significa que la optimización final consiste en soluciones de suboptimización. Se supone que estos problemas tienen una estructura ascendente.

Tome el problema de la subsecuencia común más larga, por ejemplo. Se resuelve aumentando la secuencia carácter por carácter. Cada paso registramos la respuesta de optimización para cada subsecuencia y luego llegamos a la respuesta final. Entonces este es un método de abajo hacia arriba. En esos pasos, la memorización es la clave.

La programación dinámica resuelve problemas con la “subestructura óptima”, cuando la solución a un problema en un conjunto más grande puede representarse eficientemente en términos de una solución a un problema en un conjunto incrementalmente más pequeño.

Un ejemplo simple es el algoritmo de Dijkstra para el problema de la ruta más corta. La subestructura óptima en ese caso es la siguiente: la ruta más corta entre una fuente S y un destino D se puede expresar en términos de la ruta más corta desde S a un nodo intermedio Q que está adyacente a D. En términos de un poco de matemática ( SP = ruta más corta, EW = peso del borde):

SP (S a D) = min sobre todo Q [ SP (S a Q) + EW (Q a D)]

La naturaleza recursiva de esta solución: la ruta más corta se usa recursivamente en su propio cálculo; y el hecho de que SP (S a Q) es un conjunto de problemas * más corto * que SP (S a D), ya que Q está en una ruta de S a D hace que esta sea una solución de programación dinámica.

Ver http://en.wikipedia.org/wiki/Opt …

Para el registro, no me considero un maestro, pero sí resuelvo problemas, así es como funciona el problema para algunos subestados que pueden usarse para resolver un estado de problema real. El algoritmo funciona dividiendo un solo problema grande en estados problemáticos más pequeños, resolviendo los problemas anteriores y construyéndose a partir de esto conduce a una eventual solución efectiva. A veces es fácil relacionar los problemas con los demás, por ejemplo, anoche reconocí que este es el problema de la moneda: igual solo resuelve tantos como puedas y puedes “ver” cuál es el problema, yo en un punto donde puedo Indique fácilmente un problema justo después de leer un problema (para aquellos que conozco como 0-1 mochila y las variaciones de mochila).

El problema vinculado anteriormente es solo el problema de la moneda, por lo que se puede resolver desde ese punto de partida.

Consulte este sitio web para conocer los pasos apropiados que necesita para resolver estos problemas dinámicos.

Tutorial para programación dinámica

En caso de que necesite más ayuda profesional y necesite ayuda con su ayuda de asignación de programación dinámica, puede probar asignaciones4u.com.

Buena suerte

Esta es una buena serie de videos que definitivamente mejorarán tus habilidades en dp, y geeks for geeks se querrá leer entonces;

Programación dinámica

Como no está definiendo ningún problema específico aquí, supongo que se refiere al tema en general.
En cuyo caso, tendría que decir ¡Practica!
Esto no es algo que dominar rápidamente y, como sucede con muchas otras áreas de la vida, un maestro es alguien que ha pasado muchos años aprendiendo primero.
Así que encuentre problemas específicos para abordar, busque buenos maestros y continúe resolviéndolos.

La mejor de las suertes

Salto de línea en el texto: ¿cómo se dividen las líneas de manera óptima dentro de un párrafo para minimizar el espacio perdido?