Programarea dinamică (DP) rezolvă probleme cu subprobleme suprapuse și structură de suboptimalitate calculând fiecare subproblemă o singură dată și reutilizând rezultatul. Cele două stiluri sunt memoizarea (top-down) și tabularea (bottom-up).
Ideea
Recursia naivă recalculează aceleași subprobleme exponențial. DP le pune în cache, transformând munca exponențială în una polinomială.
