¿Por qué lucho con la programación dinámica?

Answer 1

DP, supongo que es naturalmente difícil. Al igual que los hilos, en realidad tienes que pensar para trabajar con ellos. Recomiendo practicar. También recomiendo no pensar demasiado en ello. Hay una especie de magia en ello.

Por ejemplo, digamos que estoy resolviendo un problema que tiene una implementación ingenua, que hace los pasos A, B y C. Digamos que B y C se superponen, de alguna manera. ¿Qué debo hacer? Resumo, por supuesto.

No voy a completar el problema en un solo paso. Supongo que es una solución “dinámica” y veo lo que hace. Encuentre una manera de reutilizar una solución a un subproblema para resolver otro. Entonces mira lo que pasa. Use la deducción para averiguar qué hizo mal. Entonces eres dorado.

DP se trata de “ver” patrones de manera abstracta, como esto necesita eso, o aquí hay una duplicación, o aquí hay una repetición, o aquí, en este paso en la ejecución del algoritmo, los datos se arruinan. Luego agrega una pequeña solución y saca la basura después.

Aunque esté trabajando con código complejo, realmente no lo comprende. Nadie hace. Cuando domines este tipo de cosas, igual lo verás como magia, pero tú eres el mago. Soluciones automáticas: hurra.

Un pequeño paso a la vez, una pequeña mejora a la vez, y obtendrás una única solución. Planear todo el DP en tu cabeza es una locura, y las personas que muestran su conjunto de habilidades para hacerlo son solo idiotas delirantes. Tan pronto como encuentren un problema real, que es tan grande que no puede caber dentro de la cabeza de nadie, ni remotamente, su enfoque de todo a la vez será vergonzosamente corto. Pero su método de pequeños pasos los destruirá.

Preocuparse menos; programa más. Hay muchos problemas de ejemplo en la web. No puedo recomendar uno sobre otro. Hay tantos buenos que me aburro solo de pensarlo. Para eso es Google. SÍ, Google!

Answer 2

Aquí hay algunos problemas sencillos de práctica de programación dinámica.

Lea también estas respuestas:

La respuesta de Michal Danilák a ¿Cómo descubro cómo iterar sobre los parámetros y escribir soluciones ascendentes a problemas relacionados con la programación dinámica?

La respuesta de Michal Danilák a ¿Cuáles son las formas sistemáticas de preparación para la programación dinámica?

Answer 3

Aquí hay una lección en línea que puede probar https://codility.com/programmers …

Puedes probar el siguiente esquema:

• Agregue algunos parámetros al problema que está tratando de resolver.
  Ahora, en lugar de un problema, tiene que resolver un conjunto completo de problemas.
• Encuentre dependencias entre los problemas (parametrizados), para que pueda calcular sus soluciones en algún orden.
• Intenta mejorar tu parametrización o dependencias. Por ejemplo:
  – ¿Puedes tener menos problemas parametrizados para resolver?
  – ¿Se pueden calcular las dependencias más rápido?

• Diseñe una estructura de datos para almacenar soluciones a todos los problemas parametrizados que tiene que calcular. (Por lo general, algún tipo de matriz o un par de matrices). ¿Tiene que recordar todas las soluciones (por ejemplo, almacenar la matriz completa frente a una fila)?
• Codifícalo.