How to Think in Dynamic Programming (part 2)

In part one we explained what is DP and why is it handy in optimizing certain types of problems.
In this part we will delve deeper in how to find a DP solution to problems, in a systematic way by unraveling the mysterious aspect of those solutions. Usually when looking at solutions on the internet the natural reaction is how did they think of that?

As said in part one, DP is about optimization. This means there should already be a certain solution to optimize. The best solution to optimize is the “brute force” solution, in which…