Last Updated: May 24, 2019
· jg2019

Determining if a problem can be solved using dynamic programming....

To determine whether we can optimize a problem using dynamic programming, we can look at both formal criteria of DP problems. I’ll also give you a shortcut in a second that will make these problems much quicker to identify.

Let’s start with the formal definition.

A problem can be optimized using dynamic programming if it:

has an optimal substructure.
has overlapping subproblems.
If a problem meets those two criteria, then we know for a fact that it can be optimized using dynamic programming.