Dynamic Programming Problem
Hi all, I'm a bit stuck on a certain dynamic programming problem from the USACO training pages
The problem statement is as follows:
GivenV denominations of coins values, and a target valueN, determine how many the total number of unique ways to construct N amount of money using the coin denominations given.
Right now, my algorithm loops through all integer amounts of money, from 0 to N, calculates the total number of combinations possible for that particular amount of money, and stores it into an array of size N+1. The answer would be the last element of the array (element N). I believe I am correct so far.
The problem I'm running into is calculating the number of combinations possible for each amount of money. If you look at my code, you'll probably see the problem:
dp[0] = 1;
for(int i = 1; i < n; i++ ){// loop through all monetary amounts up to N
b =newboolean[n];// boolean array to store denominations previously visited
for(int j = 0; j < V; j++ ){// loops through all coin denominations
t = i-denoms[j];// calculates the value I need to add to the denomination to reach the monetary amount
if( t >= 0 && ! b[denoms[j]] ){// if t is greater than zero and coin denomination has not been previously visited
dp[i] += dp[t];// adds to number of total combinations, the number of combinations possible to make t
b[t] =true;// marks t to be visited
}
}
}
If you haven't figured out already, the problem I'm running into is as follows:
When I'm adding number of ways to make variable t to the total number of combinations, I sometimes add different permutations of the same combination (same coins used, but different order).
How can I solve this problem efficiently?
