algorithm - The minimum number of coins the sum of which is S

Question

Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.

I try to understand dynamic programming, haven't figured it out. I don't understand the given explanation, so maybe you can throw me a few hints how to program this task? No code, just ideas where I should start.

Thanks.

Answer 1

The precise answer to this problem is well explained here. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg