Algorithms – Dynamic Programming

I have been coding for some time now and yet, I feel confused when I get into a discussion about the core algorithmic concepts. I still can’t figure out if a problem needs a Dynamic Programming solution, or if its needs a divide and conquer treatment or if it should fall under a different category. This article is just an attempt to convey my level of understanding of the intuition behind Dynamic Programming. Feel free to weigh in!.

Before we discuss DP,lets try to understand the following two terms that we often associate with it.

What is Optimal Substructure?When the optimal solution to a problem can be determined utilizing the optimal solutions to its sub-problems, the problems is said to have an optimal substructure.

What are Sub-Problems?A problem is broken down into smaller problems (of smaller input size ) for the ease of computation. They are called as sub-problems. Each sub-problem is further broken down into even smaller sub-problems. This process is repeated until we reach a point where the solution to the sub-problem is easy to compute. Finally, the solutions to these sub-problems are combined to get the final solution (of the original problem).

Dynamic Programming is a rather ambiguous term. It does not give us any semantic clue as to how the technique might work which is in contrast to other techniques like divide&conquer and greedy approach.

An interesting feature of DP is the presence of overlapping sub-problems. Recognizing such overlapping sub-problems is the key to solving DP problems. DP has two main approaches, a bottom-up iterative approach known as tabulation and a top-down recursive approach known as memoization.

In the tabulation approach, we don’t actually worry about the specific problem in hand. You start small and slowly make your way up. It is more or less a blind approach where we find solutions to the smaller problems, store their results in a table and utilize these stored results to find solutions to the bigger problems. Bottom- up approach helps us get rid of the recursive overhead as the problems are generally solved without the use of recursion. Finding the right sub-problem to start with can be a problem for some people.

If recursion is your strong point, memoization would better suit you. Here, we start from the specific problem we want to solve, recursively call the sub-problems. Once the sub-problems return their results, we combine them to form our final solution. If many of your recursive calls solve the same sub-problem, it makes sense to store the sub-problem’s result the first time it is evaluated. The subsequent calls to this sub-problem can utilize the stored result. This technique is called as memoization.

Another important feature of DP is the presence of an optimal substructure. It essentially means that we need to find and store only the optimal solution of each sub-problem rather than considering all the different solutions that are possible for the sub-problem. When we combine the optimal solutions of all the sub-problems, we are guaranteed to get the optimal solution for the original problem.

Please do remember that not all recursions are DP. Recursion is just a programming technique where a function calls itself directly or indirectly. It is just that memoization approach in DP is solved using the recursive technique. Again, just because you solve a problem in a top down manner doesn’t qualify it as DP. All problems with sub-problems are also not DP unless there are overlapping sub-problems.

When you encounter a problem, first check if it is solvable in a top-down manner. Imagine the recursion tree with all the sub-problems and try to find out whether some of these sub-problems overlap. Also, make sure that combining the optimal solutions of the sub-problems will yield the optimal solution of the original problem. This can be done by trying to find a counter example. If you are unable to find a counter example, then BINGO!, you should be able to deploy a DP solution to the problem. Now, It is up to you to choose between tabulation and memoization. It does not mean that you would always be able to figure out a solution using a top down approach. Sometimes it helps to consider a tabular approach and tackling the problem bottom up.

Usually, the top-down recursive approach is more intuitive than the bottom-up approach. It is easier to mathematically understand the correctness of the algorithm. But tabulation (iterative DP) could be more efficient than memoization for some problems and the opposite is true for certain other problems. My personal experience tells me that the recursive approach has more stack allocation overhead and tend to be a bit slower than the bottom-up one. Even though we solve each and every sub-problem (even the redundant ones ) in the tabulation method, there are always ways to optimize it.

Hence once cannot authoritatively say that one is better than the other. Understanding the theory behind DP can only take your expertise to a certain extent. The only way to master DP is by practice. Try to solve as many problems as possible and slowly you will see yourself being able to identify problems that require a DP solution.