Coin Change

题目
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];
    }
}