¿Qué es el algoritmo dp?

El algoritmo DP es un método común para resolver problemas de optimización de procesos de toma de decisiones de varias etapas.

El proceso de decisión de varios pasos (proceso de decisión de varios pasos) se refiere a un tipo especial de proceso de actividad. El proceso se puede descomponer en varias etapas interconectadas en orden cronológico, y se debe tomar una decisión en cada etapa. Todo el proceso de toma de decisiones es una secuencia de toma de decisiones. El algoritmo de programación dinámica es un método comúnmente utilizado para resolver problemas de optimización del proceso de toma de decisiones en varias etapas. Es relativamente difícil y altamente técnico. Los algoritmos de programación dinámica se pueden utilizar para resolver de manera elegante y eficiente muchos problemas que no pueden resolverse mediante algoritmos codiciosos o algoritmos de divide y vencerás.

La idea básica del algoritmo de programación dinámica es: descomponer el problema a resolver en varios subproblemas interconectados, resolver los subproblemas primero y luego obtener la solución al problema original del soluciones de estos subproblemas para subproblemas repetidos que surgen, solo los resolvemos la primera vez que los encontramos y guardamos las respuestas para que podamos hacer referencia directa a las respuestas cuando las volvamos a encontrar en el futuro sin tener que hacerlo; resolverlos nuevamente. El algoritmo de programación dinámica considera la solución del problema como el resultado de una serie de decisiones. A diferencia del algoritmo codicioso, en el algoritmo de programación dinámica se toma una decisión irrevocable cada vez que se adopta el criterio codicioso; También es necesario examinar si cada secuencia de decisión óptima contiene una subsecuencia de decisión óptima, es decir, si el problema tiene propiedades de subestructura óptimas.