Questions for DP and recursion
Hi, I have a few questions about these two algorithms. Below is my recognition.
Recursive is a kind of algorithm that the highest problem will be calculated first,
and then the second high problems, a sense of "top-down" processing. And, on the contrary, DP is a kind of "bottom-up" algorithm.
In the textbook, there are 3 or 4 steps for dealing a DP problem:
Step1: Characterize the (optimal) structure
Step2: Recursive solution
Step3: Compute the optimal cost
Step4: Construct the fastest way(optional)
So, my questions are:
1. I can't really tell the difference between DP and Divide&Conquer. They both seem to cut the original problem into pieces of subproblems initially, until the subproblems become trivial.
2. What does "optimal structure" in step 1 really mean? And how can it be characterized?
3. Why is there a "recursive solution" in step 2 ? Aren't recursion and DP two different concepts?
4. In simple cases, I can tell DP is a bottom-up way, but in some more complicated problems I have no idea why it is a "bottom-up" algorithm.
5. Is memory usage necessary in DP process?
Hope these big questions can be solved, I've been confused for a week!
Thx in advance!
Recursive is a kind of algorithm that the highest problem will be calculated first,
and then the second high problems, a sense of "top-down" processing. And, on the contrary, DP is a kind of "bottom-up" algorithm.
In the textbook, there are 3 or 4 steps for dealing a DP problem:
Step1: Characterize the (optimal) structure
Step2: Recursive solution
Step3: Compute the optimal cost
Step4: Construct the fastest way(optional)
So, my questions are:
1. I can't really tell the difference between DP and Divide&Conquer. They both seem to cut the original problem into pieces of subproblems initially, until the subproblems become trivial.
2. What does "optimal structure" in step 1 really mean? And how can it be characterized?
3. Why is there a "recursive solution" in step 2 ? Aren't recursion and DP two different concepts?
4. In simple cases, I can tell DP is a bottom-up way, but in some more complicated problems I have no idea why it is a "bottom-up" algorithm.
5. Is memory usage necessary in DP process?
Hope these big questions can be solved, I've been confused for a week!
Thx in advance!
Last edited on
I will circle back on this but right away:
recursion can be used in a DP design. Its like saying 'I asked you to sort that array and you used a loop instead of a sorting algorithm'. Recursion is just a loop with a stack data structure. that is all it is. It may or may not be useful to implement a given algorithm. So you have to get this part down, #3, before you can move on to the rest of it (which I don't have the energy for tonight). Just keep repeating that to yourself.... recursion is a fancy loop and a stack... say it like 100 times or something :)
it turns out that DP usually has recursion. Maybe always, I dunno… AFAIK all recursion can be turned to iteration if you are willing to beat your head over it.
recursion can be used in a DP design. Its like saying 'I asked you to sort that array and you used a loop instead of a sorting algorithm'. Recursion is just a loop with a stack data structure. that is all it is. It may or may not be useful to implement a given algorithm. So you have to get this part down, #3, before you can move on to the rest of it (which I don't have the energy for tonight). Just keep repeating that to yourself.... recursion is a fancy loop and a stack... say it like 100 times or something :)
it turns out that DP usually has recursion. Maybe always, I dunno… AFAIK all recursion can be turned to iteration if you are willing to beat your head over it.
Topic archived. No new replies allowed.