Introduction
Dynamic Programming(DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to the subproblems.
If an issue can be broken down into subproblems, which are then broken down into smaller subproblems, and if these subproblems overlap, the answers to these subproblems can be preserved for future use.
Dynamic programming works by saving the results of subproblems so that we don’t have to recalculate them when their solutions are needed.
Dynamic Programming is a technique in computer programming that helps to efficiently solve a class of problems that have overlapping subproblems and optimal substructure property.
How Dynamic Programming Works
Dynamic programming works by storing the result of subproblems so that when their solutions are required, they are at hand and we do not need to recalculate them.
This technique of storing the value of subproblems is called memoization. By saving the values in the array, we save time for computations of sub-problems we have already come across.
Dynamic programming by memoization is a top-down approach to dynamic programming. By reversing the direction in which the algorithm works i.e. by starting from the base case and working towards the solution, we can also implement dynamic programming in a bottom-up manner.
What are Sub-Problems?
Sub-problems are smaller versions of the original problem. Let’s see an example. With the equation below:
1 + 2 + 3 + 4
1+2+3+4
We can break this down to:
1 + 2
1+2
3 + 4
3+4
Once we solve these two smaller problems, we can add the solutions to these sub-problems to find the solution to the overall problem.
Notice how these sub-problems breaks down the original problem into components that build up the solution. This is a small example but it illustrates the beauty of Dynamic Programming well. If we expand the problem to adding 100’s of numbers it becomes clearer why we need Dynamic Programming. Take this example:
6 + 5 + 3 + 3 + 2 + 4 + 6 + 5
6+5+3+3+2+4+6+5
We have 6 + 56+5 twice. The first time we see it, we work out 6 + 56+5. When we see it the second time we think to ourselves:
“Ah, 6 + 5. I’ve seen this before. It’s 11!”
In Dynamic Programming we store the solution to the problem so we do not need to recalculate it. By finding the solutions for every single sub-problem, we can tackle the original problem itself.
Recursion vs Dynamic Programming
Dynamic programming is mostly applied to recursive algorithms. This is not a coincidence, most optimization problems require recursion and dynamic programming is used for optimization.
But not all problems that use recursion can use Dynamic Programming. Unless there is a presence of overlapping subproblems like in the fibonacci sequence problem, a recursion can only reach the solution using a divide and conquer approach.
That is the reason why a recursive algorithm like Merge Sort cannot use Dynamic Programming, because the subproblems are not overlapping in any way.
Conclusion
Unlike specific coding syntax or design patterns, dynamic programming isn’t a particular algorithm but a way of thinking. Therefore, the technique takes many forms when it comes to implementation.
The main idea of dynamic programming is to consider a significant problem and break it into smaller, individualized components. When it comes to implementation, optimal techniques rely on data storage and reuse to increase algorithm efficiency. As we’ll see, many questions in software development are solved using various forms of dynamic programming. The trick is recognizing when optimal solutions can be devised using a simple variable or require a sophisticated data structure or algorithm.
