• Metodología de resolución de problemas de optimización donde se busca maximizar o minimizar cierto resultado.
• Divide problemas en subproblemas con una jerarquía entre ellos (de menor a mayor tamaño) y cada subproblema puede ser utilizado o reutilizado en diferentes subproblemas mayores.
• Para que un problema pueda resolverse de forma óptima mediante un algoritmo de este tipo, debe contar con las propiedades de subestructura óptima (presente en un problema si la solución global del mismo contiene soluciones óptimas de sus subproblemas) y subproblemas superpuestos (si en la resolución de sus subproblemas vuelven a aparecer subproblemas previamente calculados).
• Pueden resolverse recursivamente, cada subproblema se ramifica en un conjunto de subproblemas menores.
• Con una ecuación de recurrencia los caracterizamos y calculamos su compleidad temporal, donde cada término es definido como una función de términos anteriores.
• Existe uno o varios casos base desde los cuales se calculan los siguientes.
• Es fundamental el uso de la memorizacion, almacenando resultados de subproblemas previamente calculados, evitando asi volver a resolverlos y relacionandose con la propiedad de subproblemas superpuestos.
• Podemos calcular la primera vez el resultado para luego utilizarlo.
• Almacenaremos en una tabla los subproblemas resueltos.
• Expresiones recursivas dificultan la memorización, podemos resolver los subproblemas pequeños primero hacia los más grandes.
• Si para cada subproblema almacenamos cuál fue su óptimo, podriamos reconstruir las elecciones partiendo desde el caso más grande hacia atrás.

Borrador TP1

$$ Opt[i] = max(Opt[j]) + 1 \\ \text{Con j un puente compatible a i, además j < i} $$