Dynamic Programming

Dynamic Programming

When the sub-problems are dependent on each other, we do not know which splitting points are optimal. Dynamic Programming may be a better way to go. It is aimed at finding the optimal partitions by trying all possibilities.

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map, etc.). So the next time the same sub- problem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time.

Those who cannot remember the past are condemned to repeat it. — Dynamic Programming

Here’s a brilliant explanation on the concept of Dynamic Programming on Quora — Jonathan Paulson’s answer to How should I explain dynamic programming to a 4-year-old?

*writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper*
"What's that equal to?"
*counting* "Eight!"
*writes down another "1+" on the left*
"What about that?"
*quickly* "Nine!"
"How'd you know it was nine so fast?"
"You just added one more"
"So you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"