¿Qué debo hacer para mejorar el pensamiento algorítmico, especialmente para la programación dinámica?

Resolución de problemas

Estos dos pasos son la base de la resolución de problemas. Específicamente, programación de recursión, división y conquista y dinámica.

1. Divida un problema en subproblemas similares y más pequeños.
2. Dada la solución para los subproblemas, encuentre la solución para el problema principal.

También debe aprender a ver y abordar los problemas de arriba hacia abajo o de abajo hacia arriba.

• Cómo modificar Floyd Warshall para resolver Codeforces # 179 Div.1 B Greg y Graph
• ¿Cómo se explica el algoritmo de Metropolis-Hastings en términos simples?
• ¿Qué es la eficiencia del algoritmo?
• ¿Cuáles son algunas características de los datos de imágenes faciales que se pueden utilizar para alimentar los algoritmos de aprendizaje automático?
• Cómo resolver este problema con un árbol de segmentos o BIT

1. De arriba hacia abajo: resuelva el problema principal parcialmente para obtener nuevos subproblemas y una solución parcial. Repita el proceso de descomponer el problema y enriquecer la solución hasta que los subproblemas más pequeños tengan la solución acumulativa de los subproblemas más grandes.
2. De abajo hacia arriba: resuelva los subproblemas más pequeños primero y use su solución para resolver el siguiente subproblema más grande. Repita hasta que resuelva el problema principal.

Programación dinámica

Puede aplicar programación dinámica siempre que observe que

1. existe una subestructura óptima, es decir, dadas las soluciones óptimas para los subproblemas, puede encontrar la solución óptima para el problema principal.
2. Los subproblemas se repiten.

Como los subproblemas se repiten, tiene sentido recordar y reutilizar las soluciones en lugar de calcularlas una y otra vez. Ahora, este recuerdo se conoce como almacenamiento en caché, memorización o tabulación (según el autor y el enfoque de arriba hacia abajo o de abajo hacia arriba). Realmente no tienes que preocuparte tanto por la terminología.

Dependiendo de la naturaleza del problema, puede recordar las soluciones intermedias utilizando

1. una variable
2. una matriz 1D
3. una matriz 2D
4. …

Por último, si bien no menos importante

Vea si ayuda a resolver el problema en direcciones opuestas o múltiples. Por ejemplo:

1. Resolver desde el extremo derecho de la matriz en lugar de la izquierda.
2. Resuelva usando ambos extremos de la matriz en lugar de solo uno.
3. Resuelva desde el elemento inferior derecho de la matriz 2D en lugar de desde la parte superior izquierda.
4. Resuelva desde el elemento superior derecho de la matriz 2D en lugar de desde la parte superior izquierda.
5. …