What is Dynamic Programming?

Dynamic programming, when referring to the field of computer science, describes a group of similar computer algorithms meant to solve complex problems by breaking the problem down into sets of smaller problems. First created by Richard Bellman in the 1950s, dynamic programming works with problems that are either overlapping subproblems or optimal substructures. To understand how dynamic programming works, it's best to understand the concept behind these two terms.

Overlapping subproblems describe complicated equations which, when broken down into smaller sets of equations, reuse parts of the smaller equations more than once to reach an answer. For example, a mathematical equation told to calculate all possible results using a set of numbers may calculate the same result numerous times while calculating other results only one time. Dynamic programming would tell this problem that after calculating the result the first time it should save that result and plug the answer into the equation later on instead of calculating it again. When dealing with long complex processes and equations, this saves time and creates a faster solution using far fewer steps.

Optimal substructures create a solution by finding the best answer to all subproblems and then creating the best overall answer. After breaking down a complex problem into smaller problems, the computer then uses a mathematical system to determine what the best answer for each problem is. It calculates the answer to the original problem from the smaller answers. Flaws do exist with this process. While it gives the solution that works the best mathematically, it may or may not be the best solution in real life, depending on the type of problem and how it relates to the real world.

During any of these operations, the dynamic programming algorithm tries to find the shortest path to the solution. It can take one of two approaches to do this. The top-down approach breaks the equation down into smaller equations and reuses the answers for these equations when necessary. The bottom-up approach tries to solve the smallest mathematical value after breaking the equation down and then works its way up toward the largest from there. Both approaches save time, but dynamic programming only works when the original problem can break down into smaller equations that at some point are reused to solve the equation.