Dynamic Programming : Divide and Conquer

Divide and Conquer is a technique used to solve approximately 25 percent of problems humans have discovered so far. This uses recursion , iteration and dynamic programming to get solutions. This article covers what dynamic programming is and its types.

Prerequisites: This blog assumes you contain the power to think with an open mind and bears some knowledge on recursion.

Quick Brief on Recursion:

Just a heads-up: if you know what recursion is you can jump to the next heading :)

Recursion is a process which helps write a function and call it again and again with smaller sets of problems to get answers for a bigger set. The components of recursion are:

1. Identifying sets: Let’s say you have to check if a string is palindrome. One property that a palindrome consists of is that if you remove the first and last element then it should also be a palindrome. You can make use of this property to make sets. You will start with a larger string and make smaller sets by removing first and last characters and checking if those are same and left string is also palindrome.
2. Recursive function- for the above mentioned example the recursive function will check if the first and last character is the same and then check whether the substring left is palindrome or not.
   f(a[n]) = f(a[1-(n-2)])&(a[0]==a[n-1])
3. Base condition: base condition will be whether string is of length 0 or length 1. if any of these two things come, return true.

With indirect or direct recursion you can make your code look beautiful and small and help yourself solve questions faster. But make sure as there comes overheads for using recursion, as it eats up stack memory. Find pointers on Recursion Vs Iteration Below:

Recursion Vs Loops

Shift from Recursion to Dynamic Programming:-

In recursion there is a simple principle that is to solve different subsets and get an answer for the final set. There is a high possibility that you end up solving different subsets multiple times thus wasting your computer. This can be solved by storing outputs of those subsets and using those values again rather than computing them. This is done by sharing the variables used to store those values across all processes of recursion and lets say one process of iteration and updating values as soon as they are compared to skip the next computation for the same subset. This process of storing values and reusing it is known as dynamic programming. Following is an example attached for a shift from recursion to dynamic programming:

Recursion to Dynamic Programming

In this diagram on the right side you can save computation for red sides. In this you would say that this is too less of a saving but just think about in a bigger picture you are saving a very large picture :)

{
"Doubt" : "Can every recursion converted to dynamic programming?",
"Answer" : "Yes!!"
}

There are different ways you can achieve it. You can find that in sections below:

Top-Down Approach(aka Memoization):-

This is the first approach a person learns post doing recursion . This is nothing but a recursive method along with memoization. In this approach you see a bigger set which is to be calculated and while going from that set to calculating smaller subsets you preserve the values and thus saves the recomputation of that subsets. I won’t give the regular fibonacci example. For understanding you can consider that for the sake of learning dynamic programming you will start with reading stuff about dynamic programming directly and wherever there are concepts related to other topics you will stop that part, read other topics first and then come back and continue learning DP. This is not a proper example of DP but fits well for understanding top down approach. Another way to approach this is you first learn all the concepts required to solve problems related to dynamic programming and then start learning dynamic programming. There comes the second approach that is bottom up.

Bottom-up Approach(aka Tabulation):

In this method you will have to find smaller subsets that will be needed to calculate the final set and then iterate over those subsets to get to the final set. Thus this is often called tabulation because you store every subsets value in some order and then iterate over it to get to the final set. The main power that this method provides is the way you are using it to iterate over sets and thus you can play with complexity as well as space in this method. There are ways you can get space complexity from orders of n to order O(1) like in fibonacci you need to save only the last two values and not the whole to get to the answer. This is possible in a top-down approach also but is more easy in bottom-up.

Top-Down Vs Bottom-Up

I am attaching some questions below. You can try these with recursion first and then attempt with dynamic programming. You will see for larger sets you will be getting very fast results.

1. Longest Common Subsequence
2. Minimum Partition
3. Longest Path In Matrix
4. 0–1 Knapsack Problem
5. Boolean Parenthesization Problem
6. Matrix Chain Multiplication
7. Rod Cutting
8. Coin change problem

Conclusion

This article guides your shift from recursion to dynamic programming and gives you insights on how dynamic programming is a must to know tool that would help to solve a larger set of problems that you will face in your journey of competitive programming. Enjoy!!

To learn programming click here