I read it in undergrad, thought about it and did not understand why it works !
I read it during my grad, thought about it and got some understanding!
I think about it often and to this day, I am gaining an insight into it!
My insight
What is dynamic programming?
Its a bottom up approach to solve problems. And now, whats the notion of 'bottom up approach'? In simple terms, you break the problem into small parts. Then you start with those smaller constituents of the problem, and combine them one after the other and finally, after combining all the constituents, your solution is ready.
Wait! I thought that was divide and conquer.
Or err ... that is recursion dude, you ain't know nothing.
True indeed. This matches with the notion of divide and conquer technique. And divide and conquer can be formulated by recursion. If you have understood this, its time for you to know about another great truth.
In dynamic programming, the smaller constituents or sub-problems OVERLAP!
[I am going off your blog. Thinking intuitively , huh and all you could give me was bookish gibberish which I cannot comprehend.]
Wait! This is not gibberish and it is one of the two most important truths of DP. Let me explain it through an example. Do you know binary search and how we split the array into half each time during binary search? Remember that innocuous looking algorithm of binary search that is considered to be one of the most beautiful things on this planet existing within a dimension of log n time.
I hope you do remember that algorithm. If you don't, please go, read it and then come back. Now for those of you who are waiting for me to go further, here it is:
In binary search, you split the array into two equal halves, say L and R during one search. The number that you are searching for is either in L or in R. It cannot be in both (lets consider array of distinct elements only for now). If you take a pause and think now, you broke down your search problem into smaller parts: search in part L or search in part R. But the search will be successful in one of the parts. What does that imply? Your smaller parts do not overlap. Basically, either you go to part L and search further (never coming back to R again) or you go to R , search and discard part L. There is no notion of an inter-dependence between the two smaller parts for finding the solution(in this case, searching the element).
Now do you see the notion of sub-problems overlapping! If the sub-problems overlap, we cannot get the final solution unless we solve and combine them in a certain way (bottom-up way).
Not to confuse you further, I will put out my remaining truth of DP in the next post. Do give it a look.
I read it during my grad, thought about it and got some understanding!
I think about it often and to this day, I am gaining an insight into it!
My insight
What is dynamic programming?
Its a bottom up approach to solve problems. And now, whats the notion of 'bottom up approach'? In simple terms, you break the problem into small parts. Then you start with those smaller constituents of the problem, and combine them one after the other and finally, after combining all the constituents, your solution is ready.
Wait! I thought that was divide and conquer.
Or err ... that is recursion dude, you ain't know nothing.
True indeed. This matches with the notion of divide and conquer technique. And divide and conquer can be formulated by recursion. If you have understood this, its time for you to know about another great truth.
In dynamic programming, the smaller constituents or sub-problems OVERLAP!
[I am going off your blog. Thinking intuitively , huh and all you could give me was bookish gibberish which I cannot comprehend.]
Wait! This is not gibberish and it is one of the two most important truths of DP. Let me explain it through an example. Do you know binary search and how we split the array into half each time during binary search? Remember that innocuous looking algorithm of binary search that is considered to be one of the most beautiful things on this planet existing within a dimension of log n time.
I hope you do remember that algorithm. If you don't, please go, read it and then come back. Now for those of you who are waiting for me to go further, here it is:
In binary search, you split the array into two equal halves, say L and R during one search. The number that you are searching for is either in L or in R. It cannot be in both (lets consider array of distinct elements only for now). If you take a pause and think now, you broke down your search problem into smaller parts: search in part L or search in part R. But the search will be successful in one of the parts. What does that imply? Your smaller parts do not overlap. Basically, either you go to part L and search further (never coming back to R again) or you go to R , search and discard part L. There is no notion of an inter-dependence between the two smaller parts for finding the solution(in this case, searching the element).
Now do you see the notion of sub-problems overlapping! If the sub-problems overlap, we cannot get the final solution unless we solve and combine them in a certain way (bottom-up way).
Not to confuse you further, I will put out my remaining truth of DP in the next post. Do give it a look.
No comments:
Post a Comment