Reputation: 2253
Coin changing is a popular interview question. Essentially the question means given a set of coin denominations and a total how many ways can one get the total provided there's an infinite supply of each denomination of coin.
This is my code. The logic is every time I pick a coin the problem reduces to solving for the total minus the coin.
public static int numberOfWays(int total, int[] options){
int[][] memo = new int[options.length][total+1];
for (int i = 0; i <memo.length ; i++) {
for (int j = 0; j <memo[i].length ; j++) {
if(i == 0) memo[i][j] = 1;
else if(options[i] > j ) memo[i][j] = memo[i-1][j];
else memo[i][j] = memo[i-1][j] + memo[i][j - options[i]];
}
}
return memo[options.length-1][total];
}
This works on a test case of total = 5 and options = 1, 2, 3
But fails total = 10 and options = 2, 5, 3, 6
Can someone help me understand what I'm doing wrong.
Upvotes: 1
Views: 140
Reputation: 23568
First, it's good to write out a statement of what each array element represents:
memo[i][j]
represents how many ways to make the total amountj
given only coins in denominationsoptions[0]
,options[1]
, ...,options[i]
.
Now, from that you appear to have derived a few laws:
memo[0][j]
is 1
for all j
i
greater than 0, memo[i][j]
is the same as memo[i-1][j]
whenever options[i] > j
i
greater than 0, memo[i][j]
is memo[i-1][j] + memo[i][j - options[i]]
whenever options[i] <= j
Your problem is that the first of these laws isn't true. (the second two are)
The statement "memo[0][j]
is 1
for all j
" only holds if options[0]
is 1
. If options[0]
isn't 1
, then memo[0][j]
is 1 when j
is a multiple of options[0]
, and 0 when it isn't. Using only coins of denomination 2
, you can't make 5 cents, so you should have (with the second set of data) memo[0][5] == 0
, but your program says memo[0][5] == 1
. This then throws off all your subsequent calculations.
So I'd modify your program to say:
if(i == 0) { if (j % options[i] == 0) memo[i][j] = 1;
else memo[i][j] = 0; }
else if(options[i] > j ) memo[i][j] = memo[i-1][j];
else memo[i][j] = memo[i-1][j] + memo[i][j - options[i]];
(Though on a purely stylistic note, I find that if
/else
statements that don't use braces even for a single statement are asking for errors)
Upvotes: 4