Menu
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.
414
So, we create a minCoins array - minCoins[sum+1] where minCoins[i] represents minimum number of coins required to make change for amount = i. We build up the array in bottom up manner starting with minCoins[0]. The time complexity of the Dynamic Programming solution is O(n*sum). The space complexity is O(sum).
Explanation: Minimum 4 coins required.
The coin-change problem resembles the 0-1 Knapsack Problem in Dynamic Programming. It has two versions: Finding the minimum number of coins, of certain denominations, required to make a given sum. Finding the total number of possible ways a given sum can be made from a given set of coins.
The precise answer to this problem is well explained here. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
135
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
