¿Qué significa la subestructura óptima en términos simples?

Encontré esta definición de subestructura óptima en Wikipedia.

En informática , se dice que un problema tiene una subestructura óptima si una solución óptima puede construirse eficientemente a partir de soluciones óptimas de sus subproblemas. Esta propiedad se utiliza para determinar la utilidad de la programación dinámica y los algoritmos codiciosos para un problema.

En palabras simples,

Considere que hay un problema (P1), con subproblemas (P2) dentro.
Llamemos la solución a P1 como S1 y la solución a P2 como S2.
Ahora, puede diseñar la mejor solución posible para P2, y ya lo ha hecho, y eso es S2.
Si puede diseñar con éxito la solución para P1 utilizando S2, se dice que P1 tiene una subestructura óptima .

Espero que esto ayude.

Definición de Wikipedia

En informática, se dice que un problema tiene una subestructura óptima si se puede construir una solución óptima a partir de soluciones óptimas de sus subproblemas.

Considere encontrar el camino más corto para viajar entre dos ciudades en automóvil, como se ilustra en la Figura anterior. Tal ejemplo tiene una subestructura óptima. Es decir, si la ruta más corta de A a D pasa por B y luego C, entonces la ruta más corta de B a D también debe pasar por C. Es decir, el problema de cómo llegar de B a D está anidado dentro del problema de cómo llegar de A a D.

Para resolver un problema, A a D se pueden resolver utilizando la solución calculada de B a D

Significa que una solución óptima para una instancia de un problema contiene una solución óptima para una instancia más pequeña dentro de él (un subproblema ). Por ejemplo, la forma óptima de hacer un cambio por $ 1.99 (en términos de la menor cantidad de monedas utilizadas) es usar una moneda de 1 dólar y luego encontrar la forma óptima de hacer el cambio por los $ 0.99 restantes. Si no realiza el cambio de los $ 0.99 restantes de manera óptima, el cambio general de $ 1.99 tampoco será óptimo.