Cómo comprender la recursividad en backtracking de campo profundo y todo relacionado, programación dinámica, etc.

El retroceso viene como parte de la recursividad.

Recursión: llamar a la misma función (puede ser una llamada a través de otra función).

Mientras se implementa, se puede usar de diferentes maneras.

Primer tipo: en lugar de bucle. Malo: encontrar factorial. No hay ramificación ni nada en esto. Esto se puede hacer simplemente haciendo un bucle. No recurra a la recursividad si se puede hacer con un bucle simple fácilmente. Pero este es el que mayormente todos encontraron como el primer ejemplo de recursión.

Segundo tipo: Ramificación seleccionada. Búsqueda binaria. Seleccionamos a qué ramas ir y no volvemos a seleccionar otra rama. Esto también se puede hacer con bucles fácilmente. Esto es más o menos igual que el primer tipo.

Tercer tipo: Ramificación – Divide y resuelve. Torre de Hanoi. Aquí para mover n discos desde el origen al destino, estamos dividiendo el problema como “mover discos n-1 a intermedios” “mover el último disco (el más grande) al destino” “mover discos n-1 al destino”. La primera y la última llamada nuevamente resuelven el problema de forma recursiva. Otro, por ejemplo: transversal del árbol (cualquier tipo – preorden, postorder inorder)

Cuarto tipo: retroceso. Estos también son ramificados. Pero alcanzamos sucursales solo si es necesario y se basa en el valor de retorno de la sucursal anterior. Por ejemplo: Búsqueda de árbol desordenada. Tenemos que pasar por todas las ramas en función de si la retroalimentación obtenida es un error, de la rama anterior. Siguiente ejemplo solucionador de Sudoku. Este es un mejor ejemplo que el ejemplo anterior. Vamos a ver cada posibilidad (rama) de número. Los algoritmos de búsqueda más desarrollados están ahora disponibles. Un poco más fácil de entender es el algoritmo A *. Visualice ya que cada llamada recursiva es independiente de la anterior. Esa es la clave para entender bien la recursividad / retroceso.

Hay tipos de recursión más desarrollados basados ​​en estos. Estos son los conceptos básicos.

Aprender Visualizar Practicar Repetir . No hay absolutamente ninguna alternativa para practicar. Necesita poner las manos hacia abajo y comenzar a trabajar duro. Para comprender fácilmente la programación dinámica, comience con tutoriales en video, ya que esta es la forma más rápida. Estos videos de corta duración ayudarán a comprender los problemas de programación dinámica.

Una vez que haya terminado con los tutoriales en video, comience a resolver los siguientes problemas para obtener más confianza y sentirse cómodo con la Programación dinámica. ¡Aquí también puedes visualizar los algoritmos! No olvides echarle un vistazo.

Número de Fibonacci

Suma máxima de subarreglos

Word Break Problem

Número total de posibles árboles de búsqueda binaria con teclas ‘n’

Problema de suma de subconjunto

Palindrome más corto

Palindrome Min Cut

Número mínimo de intentos para llegar desde la palabra fuente a la palabra de destino

Número mínimo de monedas para realizar el cambio.

Encuentra la ruta de costo mínimo en una matriz

Subcadena palindrómica más larga

La subsecuencia palindrómica más larga

Encuentre la longitud de la subsecuencia creciente más larga en una matriz

Subsecuencia creciente más larga O (n logn)

Subcadena común más larga

Subsecuencia común más larga

Encuentre la longitud de la subsecuencia bitónica más larga en una matriz

Para imprimir el número máximo de As usando las cuatro teclas dadas.

Problema de la mina de oro

Encuentra la distancia mínima de edición entre dos cadenas dadas

0-1 Problema de mochila

Distintas cadenas binarias de longitud n sin 1s consecutivos

Cuente todas las decodificaciones posibles de una secuencia de dígitos dada

Encuentra el número total de formas de hacer cambios usando un conjunto de monedas dado

Establecer problema de partición | Programación dinámica

Parece mucho trabajo, pero después de terminar los tutoriales en video, el resto de los problemas no debería llevar mucho tiempo. Espero haber podido ayudar.

El retroceso y la fuerza bruta son algoritmos tácticos donde el número de operaciones suele ser una función polinómica del número de nodos (n) y grado (d, alternativas en cada nodo). Desarrolle una fórmula para calcular el número de operaciones. Puede ser tan simple como d ^ (n-1). Si no puede resolverlo matemáticamente, hágalo experimentalmente. Mientras lo hace, mida el tiempo por operación. Si no tiene acceso a un temporizador de alta resolución, realice una operación un millón de veces y divida el tiempo de baja resolución por un millón. El tiempo previsto es Operaciones * TimePerOperation. Si va a detenerse en la primera solución, divida por (2 * posibles soluciones). Si el tiempo de ejecución es aceptablemente bajo, puede resolver el problema tácticamente; No necesitas una estrategia.

El paralelismo es otro enfoque táctico que la naturaleza usa comúnmente, pero que los programadores pasan por alto. Por ejemplo, para encontrar una ruta a través de una red de resistencias, la naturaleza envía una gran cantidad de electrones para encontrar una ruta a casi la velocidad de la luz. No intenta en serie un borde a la vez como un programador que encuentra una ruta a través de la misma red expresada en un gráfico. Considere usar el algoritmo de la naturaleza. El problema es que los electrones que salen no pueden decirte la ruta que tomaron.

Codicioso y dinámico son algoritmos estratégicos que no son susceptibles de predicción tan simple. Las decisiones tomadas al principio del proceso de solución afectan el tiempo de ejecución exponencialmente en lugar de polinomio. Eso es lo que hace que los problemas sean NP_Hard. Una forma de mejorar la dificultad, suponiendo que no tenga un algoritmo mejor, es preprocesar el problema de entrada para calcular las probabilidades. Cuando ejecute su algoritmo, tome decisiones basadas en esas probabilidades. Eso es lo que está haciendo el enfoque codicioso de una manera poco sofisticada. Su premisa es que una solución parcial larga tiene una mayor probabilidad de éxito que una corta. Eso es a menudo una premisa falsa. Por ejemplo, al atravesar un árbol, una decisión incorrecta en un nodo temprano puede conducir a una ruta que está a un nodo por debajo del éxito. Una ruta más corta fuera de ese nodo habría sido la elección correcta. Un conjunto de probabilidades mejor que la longitud de la ruta intermedia te habría dicho eso.

La recursión no es un algoritmo, es un detalle de implementación. Una pila no es más que una lista o matriz vinculada. No elevaría el uso de estructuras de datos básicos al nivel de llamarlo algoritmo.

La programación dinámica significa usar la solución para subproblemas para calcular la solución para el problema más grande. Comenzamos desde el problema más pequeño y avanzamos hacia problemas más grandes. Las soluciones a todos los problemas pueden almacenarse en una matriz o matriz. Entonces, al calcular la solución para un problema mayor, las soluciones para todos sus subproblemas ya están calculadas y no es necesario volver a calcularlas. Este es un enfoque de abajo hacia arriba.

Incluso en la recursión dividimos el problema en sus subproblemas, pero comenzamos desde arriba, es decir, desde el problema más grande (a diferencia de DP, donde comenzamos en el problema más pequeño). Este es un enfoque de arriba hacia abajo.

Consideremos el problema de calcular el enésimo número de Fibonacci donde FIB [1] = 0 y FIB [2] = 1. En el caso de DP, comenzaremos nuestro cálculo desde el problema más pequeño, es decir, FIB [3] y calcularemos FIB [4], FIB [5], … FIB [N]. Pero, en la recursión, comenzamos desde la FIB [N] misma y dejamos que la recursión decida qué se necesita a continuación.

Ahora viene el tema de los subproblemas superpuestos. Si se utiliza la recursividad para resolver un problema que tiene subproblemas superpuestos, terminaremos calculando lo mismo una y otra vez. Al igual que en el ejemplo de Fibonacci, FIB [N-2] se calculará dos veces (al calcular FIB [N] y al calcular FIB [N-1]). Esto conducirá a una complejidad exponencial. Pero si usamos la función de Memoization con recursión, la solución recursiva funcionará tan bien como la DP (menos la función que llama la sobrecarga), porque la solución de cada subproblema se calculará una sola vez.

Para resumir, en problemas donde no hay subproblemas superpuestos (como en el cálculo de N!), La recursividad es la misma que DP. Pero en problemas donde hay subproblemas superpuestos, Recursion + Memoization es lo mismo que DP.

En respuesta a tu otra pregunta:

La idea de DP es utilizar la solución del subproblema para calcular la solución de un problema mayor. La recursión se puede pensar en una forma de implementar esta idea. Como dije anteriormente, otra forma de implementar la idea de DP es usar una matriz / matriz para almacenar las respuestas de los subproblemas y usar bucles para calcular cada celda de la matriz. Una de las celdas contendrá la respuesta que se requiere.

Gracias por A2A

La programación dinámica es lo más fácil de implementar y un poco difícil de planificar. A partir de lo básico, deberá consultar algunos libros, como El manual de diseño de algoritmos, para aclarar el concepto.

Si no eres nuevo en la codificación, entonces puedo argumentar que conoces la programación dinámica y debes haberla implementado. Por ejemplo: el programa iterativo simple para encontrar números de Fibonacci es un ejemplo de DP.

Estudiar DP desde lo básico, esa es una pregunta que estaba en mi mente y yo también usé a Quora para recibir ayuda y le referiré esas respuestas solo porque me ayudaron y no encuentro nada que falte allí.
¿Cómo aprendo programación dinámica como novato?
Puedo agregar eso …
Recuerde las lecciones del pasado para que no tenga que volver a experimentarlas.

1. Fuerza bruta / recursión: la fuerza bruta es el último recurso. Se puede aplicar a cualquier problema y producirá una solución determinista pero generalmente mala.

2. Divide y vencerás: si crees que el problema se puede dividir en subproblemas y luego estos subproblemas resuelven colectivamente el problema principal.

3. Programación dinámica: si en Divide and Conquer sientes que la solución de un subproblema es utilizada por otro. Se aplica principalmente a problemas de optimización, donde necesita encontrar mínimos o máximos.

4. Avaricioso: si en la Programación dinámica siente que tomar las decisiones óptimas locales producirá el óptimo global, entonces no tiene que resolver todos los problemas secundarios. Las soluciones codiciosas generalmente no le dan la respuesta correcta. Además, todas las soluciones codiciosas son un subconjunto de soluciones DP, por lo que es mejor sin ellas.

Como alguien más ya mencionó, estas intuiciones vienen con el tiempo. La práctica es la clave.

Recomendaría comenzar con el capítulo de Introducción a Algoritmos (CLRS).
En términos de resolver problemas para los que aún no ha visto soluciones, comience por identificar cada problema y sus subproblemas asociados. Una forma de comenzar es observar la última “decisión” que tomó, por ejemplo, en un problema de subsecuencia común, usted decide si las dos últimas letras de la secuencia son o no parte de la subsecuencia común. Usted está buscando encontrar un paso simple (probablemente recursivo) en este punto para estudiar. Una cosa a tener en cuenta aquí es que los subproblemas deben ser óptimos para que la programación dinámica sea útil.
Una vez que comprenda la naturaleza recursiva del problema, intente construir una solución de abajo hacia arriba. Comience desde el problema más simple y luego vea qué puede construir allí. A menudo, el siguiente paso es combinar las respuestas de su primer paso para determinar la solución óptima para el segundo paso, etc.
En general, la programación dinámica consiste en enumerar de manera eficiente todas las posibilidades para encontrar la mejor al centrarse únicamente en las posibilidades que condujeron a la solución óptima de subproblemas que conducen a la solución del primer problema “grande” que está tratando de resolver.

En resumen, algunos buenos pasos a seguir son:
1. Identifique el problema y los subproblemas funcionalmente similares. Verifique si las respuestas secundarias óptimas conducen a una respuesta completa óptima, ya que esta es la base de la efectividad del estilo dinámico de programación.
2. Cree una solución recursiva al problema. Esto a menudo mostrará dónde ocurre el cálculo repetido al rastrear todos los pasos que toma la recursión.
3. Cambie la solución recursiva a la solución dinámica comenzando desde el subproblema más pequeño y construyendo soluciones más grandes de abajo hacia arriba.

Retroceso

Imprima todas las posibles soluciones al problema de N Queens
Imprima todas las posibles excursiones de caballero en un tablero de ajedrez
Magnet Puzzle
Encuentra el camino más corto en Laberinto
Encuentre la ruta más larga posible en una matriz
Encuentre la ruta desde el origen hasta el destino en una matriz que satisfaga las restricciones dadas
Encuentra el número total de caminos únicos en un laberinto desde el origen hasta el destino
Imprima todo el Camino Hamiltoniano presente en un gráfico
Imprima todas las configuraciones k-colorables del gráfico (coloración de vértice del gráfico)
Encuentra todas las permutaciones de una cadena dada
Todas las combinaciones de elementos que satisfacen las limitaciones dadas.
Encuentre todas las cadenas binarias que se pueden formar a partir de un patrón comodín dado

Divide y vencerás

Búsqueda binaria
Búsqueda ternaria vs búsqueda binaria
Búsqueda exponencial
Búsqueda de interpolación
Encuentra el número de rotaciones en una matriz ordenada circularmente
Buscar un elemento en una matriz ordenada circular
Encuentra la primera o la última aparición de un número dado en una matriz ordenada
Cuenta las apariciones de un número en una matriz ordenada con duplicados
Encuentra el elemento que falta más pequeño de una matriz ordenada
Encuentra el piso y el techo de un número en una matriz ordenada
Buscar en una matriz casi ordenada en tiempo O (logn)
Encuentra el número de 1 en una matriz binaria ordenada
Encuentra el elemento pico en una matriz
Submatriz de suma máxima usando Divide & Conquer
Encuentra el elemento mínimo y máximo en una matriz usando comparaciones mínimas
Implementar eficientemente la función de potencia | Recursiva e iterativa

Ordenar fusión
Ordenar por fusión para la lista vinculada individualmente
Recuento de inversión de una matriz
Ordenación rápida
Implementación iterativa de Quicksort
QuickSort híbrido

Programación dinámica

Introducción a la programación dinámica
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 las 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 de comodines

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

Codicioso

Problema de selección de actividad
Codificación Huffman
Problema de la supercuerda más corta
Problema de secuencia de trabajos con plazos
Coloración codiciosa del gráfico

Algoritmo de Kruskal para encontrar el árbol de expansión mínimo
Senderos más cortos de una sola fuente – Algoritmo de Dijkstra

A continuación se muestra una lista completa de todos los demás temas:

Lista de problemas – Techie Delight

Primero, sugiero mirar la respuesta de Sahil, pero pensé que abordaría la pregunta real en lugar de agitarla a mano. He enseñado programación dinámica al menos un par de veces, así que quería intervenir en esto.

Creo que a menudo tiene que ver con el apilamiento de habilidades para comprenderlo y el contexto en el que se introduce. Voy a enumerar algunas cosas que encuentro son trampas comunes.

1. La programación dinámica depende en gran medida de la comprensión de las relaciones de recurrencia que utilizamos para resolver problemas de forma recursiva. Si alguien no comprende la recursividad, esto hace que sea mucho más difícil de entender si nunca ha visto un algoritmo de división y conquista o relaciones de recurrencia.
2. Muchas veces, también depende de cómo se introduce. Si alguien aprende el análisis y demuestra algunos teoremas para algoritmos un poco más complicados que la búsqueda binaria (con respecto a los problemas de optimización), puede que tengan un salto más fácil a esto. Sé que algunos (por alguna razón) muestran técnicas de DP antes de dividir y conquistar, lo que tiene poco sentido para mí porque probablemente vieron una recurrencia en algún momento antes de esto.
3. Si toma la programación dinámica en su forma original, no es fácil de entender para aquellos que solo tienen experiencia en programación en ese momento. La forma en que hemos trasladado su contexto a la informática ha hecho que sea más fácil de entender. Por ejemplo, si busca la ecuación de Bellman: Wikipedia, incluso para alguien que ha aprendido el principio de la optimización (necesaria para que funcione DP), no es tan fácil de entender para alguien que no entiende el lenguaje que Bellman usó originalmente. programación dinámica.
4. A la gente generalmente le gusta probar cosas y ver si funcionan. La programación dinámica solo funciona con algunos problemas (ver mi punto anterior, se necesita el principio de optimización). Muchas técnicas algorítmicas que aprende al comienzo (especialmente en un programa de primer o segundo año) no se desmoronan rápidamente. Por ejemplo, un algoritmo codicioso probablemente le dará una solución factible, pero como DP puede no garantizar una solución óptima. Pero tienden a ser más simples de entender. En parte, también tiene que ver con pensar en la combinación de instancias, y los estudiantes quedan atrapados en “qué instancia es cuál”.

Estoy seguro de que hay otras razones, pero estas son algunas de las que puedo pensar fuera de mi cabeza.

¡Espero que esto ayude!

No tengo una respuesta perfecta a tu pregunta, pero aquí están las cosas que hice:

• Practique, lea muchos problemas y soluciones y asegúrese de comprender por qué la solución funciona y por qué es óptima . Creo que la mitad de resolver nuevos problemas de DP es la coincidencia de patrones con problemas vistos anteriormente. Una vez que domine esto, al idear una nueva solución para un nuevo problema que no haya visto antes, tendrá una idea de por qué funciona y por qué es óptimo.
• Trate de imaginar las tablas DP, ya sea unidimensional, bidimensional o más. Piense en cuál es el estado del subproblema que podría funcionar.
• Pruebe el enfoque de arriba hacia abajo primero. Facilita las cosas cuando no estás acostumbrado a DP. Cuando mi solución de abajo hacia arriba se vuelve demasiado complicada, todavía recurro a la implementación de arriba hacia abajo.
• Personalmente, siempre escribo una solución ascendente a menos que me vean obligado a hacerlo de otra manera. Lo hago en dos pasos: descubro los estados (y, por lo tanto, la dimensión) y decido cómo llenar de manera óptima la tabla. El segundo paso es importante porque, si se hace correctamente, a veces puede reducir una o dos dimensiones del tiempo y la complejidad de la memoria.
• Asegúrese de que absolutamente necesita una solución DP. He visto casos en los que una solución de búsqueda bruta + fuerza bruta es mejor que una solución DP 😀
• Si está haciendo esto en un entorno de competencia de programación, los límites de tiempo y memoria junto con el tamaño del problema de entrada a veces pueden ofrecer una pista sobre cuál podría ser la solución (por ejemplo, puede saber si necesita O (N) frente a O (N ^ 2) solución).
• Lo más importante: si encuentra un problema que parece más fácil y solucionable, dedique un tiempo a pensarlo y no se dé por vencido y vea la solución. Se necesita mucha práctica para dar ese “salto de pensamiento” que no podrá hacer si sigue buscando las soluciones 🙂 Después de resolver algunas, avance hacia las más difíciles.

DP generalmente es difícil de entender porque no es intuitivo. Resuelve el problema de abajo hacia arriba, que es un contador intuitivo.

La segunda razón es que muchos libros toman preguntas difíciles como ejemplo para explicar DP y el enfoque del estudiante se desvía hacia la pregunta compleja que hacia el concepto.

El siguiente libro es (mío) explica el concepto usando un ejemplo simple, y luego profundiza en ejemplos complejos.

Compre programación dinámica para entrevistas de codificación (un enfoque ascendente para la resolución de problemas) Reserve en línea a precios bajos en India

Hola,

Una de las mejores maneras de aprender programación y recursividad es consultar buenos tutoriales que nos ayudan a aprender desde cero de una manera más fácil.

He oído que hay tantos tutoriales disponibles en Internet que proporcionan tutoriales con videos y código fuente y nos ayudan a aprender cualquier lenguaje de programación que comience desde básico para avanzar de una manera más fácil.

Por cierto, he oído hablar de uno de los tutoriales que cubre todo tipo de lenguajes de programación que incluye videos con código fuente GRATIS para aquellos que se suscriben, supongo que si no me equivoco.

Aquí está el enlace @Learnsauce

La recursión es un poco complicada al principio, pero no debería serlo. Cuando escribe una función recursiva, debe tener un caso base. Ese caso base le dice si ejecutar la recursión o regresar. Es así:

para (int i = 0; i <100; i ++)

Cuando vea esto para el bucle, sabrá que ejecutará todo dentro de él siempre que sea inferior a 100.

En la recursión haces algo como esto:

public int myFunction (x) {
si (x> = 100) {
regreso;
}
//tu codigo
devuelve myFunction (x)
}

Debe aprender a separar el caso base del código real y comprenderlo realmente, entonces será mucho más fácil para usted.

Retroceder es algo que probablemente ya sepas. Intente ingresar 9 números como si fuera una fila en Sudoku e intente validarlo.

La programación dinámica es fácil. Es recurrencia con el almacenamiento de resultados anteriores. Lo primero que siempre tiene que hacer es dividir el problema en más pequeño una vez. Digamos que quieres resolver el problema de la moneda. Básicamente, tiene tres monedas 1,2 y 5 y desea saber la cantidad más pequeña de monedas que necesita para cambiar una cantidad específica de dinero. Por ejemplo, 15 dinero (llámelo dólar, ying yang, euro, lo que no importa) se cambia de manera óptima usando tres monedas de 5 monedas.

Entonces, para dividir el problema de la moneda, primero encontrará la cantidad de monedas que necesita para 1, luego 2, 3,4, … n-2, n-1, n. Todas estas pequeñas soluciones lo ayudarán a llegar a la solución final.

Lo siguiente es saber qué estructura de datos usar. En este caso, una matriz es la correcta, ya que el índice le indica la cantidad de dinero que desea cambiar y el valor en ese índice le dice cuántas monedas necesita para eso.

El último paso es la recursión. ¿Cómo será tu recursión? En este caso, su recursión devolvería lo siguiente

return min (matriz [i-1], matriz [i-2], matriz [i-5]) + 1;

Intente resolver el problema por su cuenta y tendrá sentido por qué devuelve esto.

Buena suerte y si tienes preguntas, pregúntame. Espero que esto haya sido útil. 🙂

Ya he escrito sobre temas estrechamente relacionados anteriormente, así que por favor vea

La respuesta de Shriram Krishnamurthi a ¿Se puede resolver cada problema de programación dinámica utilizando la recursividad con la memorización?

La respuesta de Shriram Krishnamurthi a Si tuviera que estudiar programación dinámica desde cero de nuevo, ¿cómo lo haría? ¿Qué recursos usarías? ¿Qué problemas resolverías? ¿Y en qué orden harías todas estas cosas?

La respuesta de Shriram Krishnamurthi a ¿Es habitual aprender algoritmos de gráficos antes de DP?

Asegúrese de leer la compensación detallada entre DP y recursión (con memorización) en mi libro, PAPL, mencionado anteriormente.

Algunos consejos que me ayudaron:

• todas las soluciones recursivas tienen sus soluciones iterativas: intente resolver una pregunta de ambas maneras;
• desde mi punto de vista, la programación dinámica no es más que recurrencia con la memorización: si puede resolver un problema de forma recursiva, lo más probable es que este problema pueda resolverse con el enfoque DP y la solución será más rápida que la recursiva; nuevamente intente practicar ambas soluciones para el mismo problema;
• para retroceder: creo que solo la práctica puede ayudar aquí;

Y algunos ejemplos que me vienen a la mente:

• retroceso: combinaciones, permutaciones, nQueens, Sudoku, conjunto de potencia
• problemas que pueden resolverse tanto con recursividad como con programación dinámica, pero para los cuales la programación dinámica tiene sentido: compruebe si una cadena es una intercalación de otras dos, coincidencia de comodines, suma mínima de ruta

Pero un consejo general: ¡nada supera a la práctica! Hay muchas fuentes con soluciones, comience desde allí.
¡Buena suerte!

Estos problemas son típicos en las preguntas de la entrevista del ingeniero de software, lo que significa que si mira el material de preparación de la entrevista, encontrará mucho ejercicio con soluciones. Recomendaría LeetCode y InterviewBit.

La programación dinámica es aplicable a problemas que exhiben las propiedades de:

• subproblemas superpuestos, y
• Subestructura óptima.

La subestructura óptima significa que puede resolver con avidez subproblemas y combinar las soluciones para resolver el problema mayor.

La diferencia entre la programación dinámica y los algoritmos codiciosos es que los subproblemas se superponen en la programación dinámica . Tan codicioso es un caso especial de programación dinámica.

En cuanto al retroceso, DP es una gran optimización en la búsqueda de retroceso. Utilizamos la memorización para erradicar los cálculos redundantes de todas las soluciones posibles en un algoritmo de retroceso.

Comience con los problemas estándar de DP como la suma de subconjuntos, la mochila, el cambio de monedas, LCS, etc. Haga códigos recursivos e iterativos para ellos y entienda cómo están funcionando. El siguiente paso es practicar tantos problemas como sea posible. Intente obtener el estado DP correcto y luego forme la recurrencia. Hay mucha variedad en los problemas de DP, por lo que cuanto más practiques, mejor resolverás un nuevo problema que se te presente.

Los problemas de retroceso y programación dinámica son en su mayoría de naturaleza recursiva. Por lo tanto, asegúrese de comprender también la recursividad. Puede practicar los problemas de recursividad que se dan aquí.

Después de comprender la recursividad, puede consultar este enlace para practicar el retroceso y este enlace para practicar DP.

También recomendaría intentar resolver los problemas usted mismo sin mirar las soluciones propuestas.

Espero que esto ayude.