Life In 19x19
http://www.lifein19x19.com/

dynamic programming: noob question
http://www.lifein19x19.com/viewtopic.php?f=8&t=14303		 Page 1 of 1
Author:  Kirby [ Fri Jun 09, 2017 11:18 am ]
Post subject:  dynamic programming: noob question
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?
Author:  dfan [ Fri Jun 09, 2017 11:36 am ]
Post subject:  Re: dynamic programming: noob question
Your approach is fine. It also avoids computing information that you don't need (you solve only the subproblems relevant to your actual problem). When I used DP for a couple of problems in the first L19 programming contest, I used your top-down approach.

Which approach I would use on any given problem varies. If I know that I'm going to need to solve every subproblem anyway, I might go bottom-up and not worry about memoization and recursion. If I knew that only a very small number of subproblems were relevant to any given top-level problem, I would definitely go top-down. For example, I would never go bottom-up on the peg-jumping problem from the first week.
Author:  Solomon [ Fri Jun 09, 2017 11:55 am ]
Post subject:  Re: dynamic programming: noob question
I'd highly recommend getting "Competitive Programming 3" by Steven and Felix Halim for answers to these kinds of questions :D. 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):

Image
Author:  Kirby [ Fri Jun 09, 2017 1:29 pm ]
Post subject:  Re: dynamic programming: noob question
Thanks. It's a relief to know that my method might still work. I think it's a good point to watch out for stack overflows with top down approach.
Author:  EdLee [ Fri Jun 09, 2017 3:24 pm ]
Post subject: 
Solomon wrote:
Competitive Programming 3
Off off-topic:
Fascinating. I was curious if competitive cooking books existed ( in addition to competitive cooking shows ); a quick search on Amazon seems to return only the TV shows. :)
Author:  fwiffo [ Fri Jun 09, 2017 4:52 pm ]
Post subject:  Re: dynamic programming: noob question
My top-down solution.
Code:
import functools

@functools.lru_cache(maxsize=None)
def min_coins(target_sum, coins):
    if target_sum == 0:
        return 0
    if target_sum < 0:
        return float('inf')
    return 1 + min(min_coins(target_sum-c, coins) for c in coins)

# min_coins(11, (1, 3, 5)) == 3
# min_coins(5, (2, 4)) == inf -- not possible
Page 1 of 1 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/