En informática , se dice que un problema tiene subproblemas superpuestos si el problema se puede dividir en subproblemas que se reutilizan varias veces o un algoritmo recursivo para el problema resuelve el mismo subproblema una y otra vez en lugar de generar siempre nuevos subproblemas. [1] [2] [3]
Por ejemplo, el problema de calcular la secuencia de Fibonacci presenta subproblemas superpuestos. El problema de calcular el n- ésimo número de Fibonacci F ( n ) se puede dividir en los subproblemas de calcular F ( n - 1) y F ( n - 2), y luego sumar los dos. El subproblema de calcular F ( n - 1) se puede dividir en sí mismo en un subproblema que implica calcular F ( n - 2). Por tanto, el cálculo de F ( n - 2) se reutiliza y, por lo tanto, la secuencia de Fibonacci presenta subproblemas superpuestos.
Un enfoque recursivo ingenuo de tal problema generalmente falla debido a una complejidad exponencial . Si el problema también comparte una propiedad de subestructura óptima , la programación dinámica es una buena forma de resolverlo.
Cuando se ejecuta, la fibonaccifunción calcula el valor de algunos de los números en la secuencia muchas veces, siguiendo un patrón que se puede visualizar en este diagrama:
Sin embargo, podemos aprovechar la memorización y cambiar la fibonaccifunción para utilizarla fibMemasí:
Esto es mucho más eficiente porque si el valor rya ha sido calculado para cierto ny almacenado fibMem[n - 1], la función puede simplemente devolver el valor almacenado en lugar de hacer más llamadas de función recursivas. Esto da como resultado un patrón que puede visualizarse mediante este diagrama: