题目
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Note: You can assume that
0 <= amount <= 5000
1 <= coin <= 5000
the number of coins is less than 500
the answer is guaranteed to fit into signed 32-bit integer
答案
class Solution {
public int coinChange(int[] coins, int M) {
// write your code here
int[] f = new int[M + 1];
f[0] = 0;
for(int i = 1; i <= M; i++) {
f[i] = Integer.MAX_VALUE;
for(int j = 0; j < coins.length; j++) {
if(i >= coins[j] && f[i - coins[j]] < Integer.MAX_VALUE) {
f[i] = Math.min(f[i], f[i - coins[j]] + 1);
}
}
}
if(f[M] == Integer.MAX_VALUE) return -1;
return f[M];
}
}
