No soy bueno en programación dinámica y no puedo hacer ni un solo problema de DP. Donde me falta

Todo lo que te falta es práctica. La mayoría de las personas encuentran difícil la programación dinámica. Con práctica puede dominar el concepto y resolver cualquier problema de programación dinámica.

Aquí hay algunas preguntas que puede probar. Este contenido me ha resultado muy útil porque puede usar la visualización de algoritmos para visualizar la solución. Esto podría ayudarlo a ver cómo se pueden guardar y utilizar eficientemente subproblemas superpuestos para resolver un problema en tiempo polinómico mediante programación dinámica.

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

Submatriz cuadrada de tamaño máximo con todos los 1

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

¡Espero que esto ayude!

DP es mi favorito. Lucho mucho con DP. Realmente, cualquier cantidad de práctica puede ser insuficiente para una buena pregunta de DP. ¡Es DEMASIADO MALDITO TRUCO!

Si está pensando que las personas son naturalmente talentosas en DP, déjeme decirle que no le ayudará de ninguna manera a compararse con los naturales. ¿Cuál es tu razón para hacer CP? Para mí, es una oportunidad para resolver problemas interesantes y difíciles.

Probablemente diferiré de la opinión popular aquí, pero aún así te aconsejaré con una pequeña cosa: no mires el editorial para DP. En serio, lea tantos tutoriales como desee, pero cuando tenga un problema, no lea la solución. Deja que te lleve una semana completa. DP es complicado, y no puedes vencerlo solo con editoriales. Tendrá que encontrar una manera de entender cómo resolver DP. No puedes estudiar sobre DP, tienes que “ver” la solución, y esa visión viene con paciencia. Claro, si tiene algún tipo de prisa por ingresar a IOI / ACM-ICPC, entonces tal vez siga la guía de inicio rápido, que es (práctica + leer editorial + mejora), pero realmente disfruté “ver” cómo funciona DP, así que si tienes tiempo, haz las dos cosas.

La parte más importante de resolver un problema de programación dinámica es comprender el problema y dividirlo en un problema en una escala mucho más pequeña. Este proceso requiere imaginación. Si no puede resolver un solo problema de DP, está claro que no está analizando el problema por completo. Solo con la comprensión adecuada y un poco de imaginación, podrá resolver un problema de DP.

Tomemos un ejemplo muy fácil de la serie Fibonacci. Si un problema es pedirle que dé, digamos, el número 100 de una serie de Fibonacci. Debes darte cuenta de lo que se requiere para obtener el centésimo término de la serie. Tienes que volver al problema mucho más pequeño, es decir, si 0 y 1 son el primer y segundo término, entonces lo que se necesita para encontrar el tercer término. Significa obtener el centésimo término, primero debe encontrar un tercer término mucho más pequeño, así que rompa el problema ya que el nuevo problema es solo encontrar el tercer término. el resto es simple cálculo. Así que trate de imaginar un problema como una versión más pequeña del mismo, es decir, para el centésimo término, imagine el problema como solo para el tercero y luego avance.

Para ser bueno en la programación dinámica, debe practicar muchos problemas de DP y pensar recursivamente.

Hay muchos problemas de medio fácil en la programación dinámica y la recursión que parecen muy difíciles cuando se abordan de la manera incorrecta, pero se ven bastante fáciles cuando se piensa en la dirección correcta usando la recursividad.

Tomemos, por ejemplo, el problema de no contar subsecuencias de la forma “101” en una cadena binaria. ex para la cadena 1001, hay dos “101” que usan el 1er, 2do y 4to carácter y usan 1er, 3er y 4to índices. Primero intente este problema por su cuenta y luego continúe y eche un vistazo a la solución. La complejidad deseada de la solución es de tamaño lineal de cadena.

Si intenta abordar este problema utilizando la recursividad y optimizarlo, encontrará fácilmente una solución elegante para el problema.

Pensando recursivamente, en cualquier punto de la cadena si el carácter en la posición actual es 1, entonces cuántos “101” puedo formar usando el 1 en la posición actual. La respuesta es el número de “10” que ocurren antes de esa posición. Entonces, reduje el problema de encontrar “101” a problema de encontrar “10”. ¿Puedo reducir más? Sí, el número de formas de formar “10” con la posición actual (si es “0”) es el número de “1” antes de esa posición.

Ahora, piense en tres funciones, f (n), g (n) y h (n). f (n) da la respuesta al problema original hasta el índice n. De manera similar, g (n) cuenta el número de “10s” hasta el enésimo índice, y h (n) cuenta el número de “1” hasta la enésima posición. Ahora, repita toda la cadena, si el carácter actual es “1”, entonces f (n) = g (n-1) + f (n-1) y h (n) + = 1. Si es “0” “, entonces g (n) = g (n- 1) + h (n) (Por lógica similar).

Por lo tanto, solo codifico estas funciones e imprimo el valor final de la función f como respuesta. Este era un problema fácil y no requería ningún truco especial, solo tenía que pensar recursivamente.

Antes de renunciar a un problema DP, hágase la pregunta.

¿Qué han intentado todos los estados para almacenar información, o qué información si hubiera demostrado ser útil para resolver una instancia más grande (en el caso anterior, tener un número de “10” demostrado ser útil)?

Por supuesto, hay muchos trucos en los problemas de programación dinámica y puede haber muchos problemas difíciles que no se pueden resolver con una recursión simple, pero esto debería darle una idea.

Deberías comenzar con la programación estática.

debe comprender lo básico de javascript en caso de programación web y

aprendes adv.java para una mejor dinámica, y es más fácil que core java.

Intente leer este enlace: Respuesta de Manohar Reddy Poreddy a ¿Cómo desarrolla relaciones recurrentes para problemas de programación dinámica?

Eso tiene respuesta sobre qué hacer.

Espero que ayude.

La mejor de las suertes.