dynamic programming: noob question

[Kirby]

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?

[dfan]

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.

[Solomon]

I'd highly recommend getting "Competitive Programming 3" by Steven and Felix Halim for answers to these kinds of questions . 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):

[Kirby]

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.

[EdLee]

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.

[fwiffo]

My top-down solution.

Code: Select all

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