La programación dinámica se utiliza para optimizar los algoritmos recursivos, ya que tienden a escalar exponencialmente. La idea principal es dividir los problemas complejos en subproblemas más pequeños y luego guardarlos en la memoria para que no tengamos que volver a calcularlos cada vez que los usamos. A diferencia de la recursión, en la programación dinámica cada subproblema distinto debe resolverse solo una vez.
Esta característica expresa que un problema de optimización se puede resolver al combinar las soluciones óptimas de los problemas secundarios que lo conforman. Estas subestructuras óptimas se describen mediante la recursividad.
El espacio de los subproblemas debe ser pequeño. Es decir, cualquier algoritmo recursivo que resuelva un problema deberá resolver los mismos subproblemas una y otra vez, en lugar de generar nuevos subproblemas.
A continuación una explicación paso a paso en programación dinámica de multiplicación de matrices:
https://programmerclick.com/article/5759945750/
Ejemplo suma de SubRectangulo:
Página 28 a 50
https://miel.unlam.edu.ar/data/contenido/1113/Programacio--n-Dina--mica_1.pdf
Explicación teórica
https://www.instintoprogramador.com.mx/2019/06/programacion-dinamica-en-java.html?m=1
Ejemplos prácticos