换硬币 -dp

换硬币

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.

样例
样例1

输入：
[1, 2, 5]
11
输出： 3
解释： 11 = 5 + 5 + 1
样例2

输入：
[2]
3
输出： -1
注意事项
你可以假设每种硬币均有无数个
总金额不会超过10000
硬币的种类数不会超过500, 每种硬币的面额不会超过100

    /**
     * coins[2,5,7]
     * 27
     * <p>
     * f(x) = min(f[x-2]+1,f[x-5]+1,f[x-7]+1)
     *
     * @param coins:  a list of integer
     * @param amount: a total amount of money amount
     * @return: the fewest number of coins that you need to make up
     */
    public static int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] f = new int[amount + 1];
        f[0] = 0;
        for (int i = 1; i <= amount; i++) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 0; j < n; 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[amount] != Integer.MAX_VALUE) {
            return f[amount];
        } else {
            return -1;
        }
    }