The essential idea of dynamic programming is to save the result for future use.
For example, if I have already know 1+2+3 equals 6 and saved the result at a place, then when I have to calculate 1+2+3+4, I just have to calculate 6+4 instead of going from scratch.
☻ ☻ ☻
On what kind of problem is dynamic programming supposed to be used? #
Those fulfill these two properties at the same time.
First, this problem has the “optimal substructure” property. In other words, it can be dealt with using “divide & conquer”, which means divide a problem into a smaller one until it can not be further divided, then conquer the small problems from bottom to top until the original one get solved.
Second, this problem has the “overlapping subproblems” property. That is to say, some results will be used in the future, and it is helpful to save them in case.
If a problem can only fulfill the first property, then use “divide & conquer” to solve it. Only if a problem can fulfill both, it is appropriate to use dynamic programming.
☻ ☻ ☻
From top to bottom vs. from bottom to top #
Solving a problem from bottom to top means we do not have to save the results on the way, so no stack is used. But this method normally requests way more time to figure out the logic behind the problem and the relationships between those temporary results.
Therefore, when you need to solve a problem quickly, then start thinking from top to bottom. Later, when you have time or interest to optimize it, maybe think about the reverse way.
🌃 Feature image: Mexican festival of the dead in Humboldt Forum, Berlin. Yinting