dynamic programming: noob question
Posted: Fri Jun 09, 2017 11:18 am
I'm trying to get the hang of dynamic programming, and was reading the tutorial here:
https://www.topcoder.com/community/data ... -advanced/
For the first beginner exercise, I tried to just think of the problem at first, before reading ahead, and think of how I might solve the problem. I found that my approach was not the same as what's described, and I was hoping to get advice for how to recognize the benefits of constructing a solution "bottom-up" vs. "top-down".
Specifically, the first question is a DP problem such that, given a list of N coins with values (V1, V2, ..., Vn) and a total sum S, find the minimum number of coins that can be used to get a sum of S.
I stopped here, and thought about how I'd try to solve the problem.
Taking their example of values (1, 3, 5) and S=11, my general approach would be as follows:
1.) See if there are any values V that are less than 11. If not, return -1.
2.) Check a hash table (for storing intermediate results) to see if I already have minimum sums for S=10, S=8, or S=6. If the hash table has no values, recursively get the minimum number of coins required for sum (11-1=10), (11-3=8), and (11-5=6), and store the results in the hash table. If the return value of any of these were unsatisfiable (i.e. -1), omit from the set.
3.) Get the minimum of the values returned from the recursive calls, and add 1. That's my minimum for the current sum S=11.
Obviously, this is different from the approach given in the article. Intuitively, I try to approach the problem "top-down". I try to start at the top sum S=11, simulate using that coin, and get the result for S-Vi for each value Vi.
The article, rather, describes a "bottom-up" approach of using states: first identify state S=0, then build on that to create state S=1, all the way up to the state for the final solution.
I have two questions:
1.) Is my approach infeasible? What are the benefits of starting "bottom-up" rather than from the "top-down"?
2.) Intuitively, I see the problem as one that requires a "top-down" approach. What aspects of a problem can I look for that would suggest a "bottom-up" approach is better?
https://www.topcoder.com/community/data ... -advanced/
For the first beginner exercise, I tried to just think of the problem at first, before reading ahead, and think of how I might solve the problem. I found that my approach was not the same as what's described, and I was hoping to get advice for how to recognize the benefits of constructing a solution "bottom-up" vs. "top-down".
Specifically, the first question is a DP problem such that, given a list of N coins with values (V1, V2, ..., Vn) and a total sum S, find the minimum number of coins that can be used to get a sum of S.
I stopped here, and thought about how I'd try to solve the problem.
Taking their example of values (1, 3, 5) and S=11, my general approach would be as follows:
1.) See if there are any values V that are less than 11. If not, return -1.
2.) Check a hash table (for storing intermediate results) to see if I already have minimum sums for S=10, S=8, or S=6. If the hash table has no values, recursively get the minimum number of coins required for sum (11-1=10), (11-3=8), and (11-5=6), and store the results in the hash table. If the return value of any of these were unsatisfiable (i.e. -1), omit from the set.
3.) Get the minimum of the values returned from the recursive calls, and add 1. That's my minimum for the current sum S=11.
Obviously, this is different from the approach given in the article. Intuitively, I try to approach the problem "top-down". I try to start at the top sum S=11, simulate using that coin, and get the result for S-Vi for each value Vi.
The article, rather, describes a "bottom-up" approach of using states: first identify state S=0, then build on that to create state S=1, all the way up to the state for the final solution.
I have two questions:
1.) Is my approach infeasible? What are the benefits of starting "bottom-up" rather than from the "top-down"?
2.) Intuitively, I see the problem as one that requires a "top-down" approach. What aspects of a problem can I look for that would suggest a "bottom-up" approach is better?
. Here is what they wrote regarding top-down vs bottom-up approaches to DP (screenshot is taken from the first edition, which is available for free on their site so it should be legal):
