java实现减治法解决n枚硬币问题

减治法是一种常见的算法设计思想，它通过将问题分解为规模更小的子问题来解决原问题。对于n枚硬币问题，我们可以使用减治法来解决。

具体实现如下：

1. 定义一个函数 coinChange(n)，其中n表示需要凑成的总金额。

2. 对于每一种硬币面值，我们可以将问题分解为两种情况：

（1）使用该硬币，凑出的金额为 n - coin[i]，此时需要进行递归调用 coinChange(n - coin[i])。

（2）不使用该硬币，这时候需要考虑其他硬币的组合方式，同样需要进行递归调用 coinChange(n)。

3. 在递归调用中，我们需要记录每一种组合方式的硬币数量，并选择最小数量的组合方式作为最终结果。

下面是Java代码实现：

public int coinChange(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    if (amount < 0) {
        return -1;
    }
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < coins.length; i++) {
        int res = coinChange(coins, amount - coins[i]);
        if (res >= 0 && res < min) {
            min = 1 + res;
        }
    }
    return (min == Integer.MAX_VALUE) ? -1 : min;
}

其中，coins表示硬币面值数组，amount表示需要凑成的总金额。在实现中，我们使用了递归调用来解决问题，并记录了最小数量的组合方式作为最终结果。