The formal definition of dynamic programming

Dynamic programming can transform an exponential-time recursion into a polynomial-time algorithm by storing and reusing answers to repeated subproblems. However, not every problem can be solved with dynamic programming. Some problems have no redundancy to exploit, while others have plenty of redundancy, but their subproblems cannot be combined safely. Dynamic programming applies precisely when two specific conditions hold simultaneously. In this lesson we will learn the formal definition of dynamic programming.

Only the problems that have both overlapping subproblems and optimal substructure can be solved with dynamic programming.

Let P be a problem instance, typically an optimisation problem with input size n.

We focus on optimisation problems here, but the framework extends to counting, decision, and reachability problems as we will see.

P is a generic problem of size n.

We say P is can have a dynamic programming solution if it satisfies the following two properties.

1. Optimal substructure

For the problem P, let OPT(P) denote the value of an optimal solution to P. We say P has optimal substructure if there exist a finite set of subproblems P1, P2, ..., Pk, each of a strictly smaller size than P, and a function combine, such that the the following holds true.