Red de conocimiento informático - Espacio del host - ¿Quieres saber qué es el algoritmo dp?

¿Quieres saber qué es el algoritmo dp?

El algoritmo DP es un método común para resolver problemas con ciertas propiedades óptimas.

En comparación con otros algoritmos, la programación dinámica reduce en gran medida la cantidad de cálculo y enriquece los resultados del cálculo. No solo encuentra el valor óptimo desde el estado actual hasta el estado objetivo, sino que también encuentra el valor óptimo desde el estado intermedio, lo cual es muy útil para muchos problemas prácticos.

En comparación con los algoritmos generales, la programación dinámica también tiene algunas desventajas: ocupa demasiado espacio, pero es sin duda el mejor método para problemas que no requieren mucho espacio. Los algoritmos de programación dinámica y los algoritmos codiciosos son métodos comunes para construir soluciones óptimas. El algoritmo de programación dinámica no tiene un modelo fijo de resolución de problemas y es altamente técnico.

La idea básica de la programación dinámica: en términos generales, siempre que el problema se pueda dividir en subproblemas más pequeños y la solución óptima del problema original contenga la solución óptima del subproblema. , se puede considerar resuelto mediante programación dinámica.

La esencia de la programación dinámica es la idea de dividir y vencer para resolver la redundancia. Por lo tanto, la programación dinámica es una estrategia algorítmica que descompone una instancia de problema en subproblemas similares más pequeños y almacena las soluciones a los subproblemas para evitar cálculos repetidos de subproblemas para resolver un problema de optimización.