Divide and Conquer versus Dynamic Programming
Let me outline two very important truths here:
In D&C, you divide the main problem, say P into smaller parts. Lets consider, for the sake of simplicity, that P is broken down into two smaller sub-problems S1 and S2. Simply think of P as being: P = S1+ S2. Now, in a pure D&C setting, you would solve S1 and S2 separately, combine their solutions in a certain way and get the answer to P. Perfect!
In DP, the first realization you should have is that S1 and S2 overlap. Lets consider that S2 depends on S1 (overlap!). This means that S1 has to be solved before S2 can be solved. Now you may ask, why? Why isn't there any other way to solve S2? Because if P is a DP problem and P has a optimal sub-structure, then its sub-problems also have a optimal sub-structure. And if S1 and S2 have a optimal sub-structure and S2 is dependent on S1, you should optimally solve S1 first which would lead you to getting a optimal solution to S2.
And how does this all say that you cannot use D&C? As a matter of fact, you can. You could solve S1 in one part, S2 in another ... in a D&C setting. But that would involve more work because you are going to solve S1 twice, once by itself and once when you are trying to solve S2. That loosely-said more-work grows exponentially as the overlapping sub-problems increase.
All that said and done, whats a simple, intuitive way to solve such a problem P which includes the notion of overlapping sub-problems and optimal sub-structure? Its simple, isn't it? Solve S1 first and remember the result. Then solve S2 utilizing the remembered result for S1 (S2 depends on S1). Then solve P using the solutions of S2 and S1. All you had to do was start from bottom (S1) and move gradually (through S2) towards up (P). That makes your computation easier, gives you a solution and a chance to boast about your DP prowess.
So long, DP!
Let me outline two very important truths here:
- D&C is a top-down approach while DP is a bottom-up approach to solve problems.
- D&C can be used to solve a problem instance of DP.
What then, is the difference, you may ask? Why DP? Why not D&C? The answer, my friend, is blowing in the wind. :)
I will give it a shot to explain this as simply as I can:
In D&C, you divide the main problem, say P into smaller parts. Lets consider, for the sake of simplicity, that P is broken down into two smaller sub-problems S1 and S2. Simply think of P as being: P = S1+ S2. Now, in a pure D&C setting, you would solve S1 and S2 separately, combine their solutions in a certain way and get the answer to P. Perfect!
In DP, the first realization you should have is that S1 and S2 overlap. Lets consider that S2 depends on S1 (overlap!). This means that S1 has to be solved before S2 can be solved. Now you may ask, why? Why isn't there any other way to solve S2? Because if P is a DP problem and P has a optimal sub-structure, then its sub-problems also have a optimal sub-structure. And if S1 and S2 have a optimal sub-structure and S2 is dependent on S1, you should optimally solve S1 first which would lead you to getting a optimal solution to S2.
And how does this all say that you cannot use D&C? As a matter of fact, you can. You could solve S1 in one part, S2 in another ... in a D&C setting. But that would involve more work because you are going to solve S1 twice, once by itself and once when you are trying to solve S2. That loosely-said more-work grows exponentially as the overlapping sub-problems increase.
All that said and done, whats a simple, intuitive way to solve such a problem P which includes the notion of overlapping sub-problems and optimal sub-structure? Its simple, isn't it? Solve S1 first and remember the result. Then solve S2 utilizing the remembered result for S1 (S2 depends on S1). Then solve P using the solutions of S2 and S1. All you had to do was start from bottom (S1) and move gradually (through S2) towards up (P). That makes your computation easier, gives you a solution and a chance to boast about your DP prowess.
So long, DP!
Very interesting and friendly description of Dynamic Programming! :D If you can give more examples of problems that can be solved by DP that would be great.
ReplyDelete