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.